Mooshak the mouse has been placed in a maze. There is a huge chunk of cheese somewhere in the maze. The maze is represented as a two-dimensional array of integers, where 0 represents walls.1 represents paths where Mooshak can move and 9 represents the huge chunk of cheese. Mooshak starts in the top left corner at 0. Write a method is Path of class Maze Path to determine if Mooshak can reach the huge chunk of cheese. The input to is Path consists of a two dimensional array and for the maze matrix. The method should return 1 if there is a path from Mooshak to the cheese. And 0 if not Mooshak is not allowed to leave the maze or climb on walls.

 Mooshak the mouse has been placed in a maze. There is a huge chunk of cheese somewhere in the maze. The maze is represented as a two-dimensional array of integers, where 0 represents walls.1 represents paths where Mooshak can move and 9 represents the huge chunk of cheese. Mooshak starts in the top left corner at 0.

 

Write a method is Path of class Maze Path to determine if Mooshak can reach the huge chunk of cheese. The input to is Path consists of a two dimensional array and for the maze matrix. The method should return 1 if there is a path from Mooshak to the cheese. And 0 if not Mooshak is not allowed to leave the maze or climb on walls.

EX: 8 by 8(8*8) matrix maze where Mooshak can get the cheese.

10111001

10001111

10000000

10109011

11101001

10101101

10000101

11111111

Test Cases:

Case 1:

Input:[[1,1,1,][9,1,1],[0,1,0]]

Expected return value :1

 

Explanation:

The piece of cheese is placed at(1,0) on the grid Mooshak can move from (0,0) to (1,0) to reach it or can move from (0,0) to (0,1) to (1,1) to (1,0) Test case 2:

Input: [[0,0,0],[9,1,1],[0,1,1]]

Expected return value: 0

Explanation:

Mooshak cannot move anywhere as there exists a wall right on (0,0)

Existing Program

/*include header files needed by your program

some library functionality may be restricted

define any function needed

function signature begins, this function is required*/ Int isPath(int **grid,int m,int n) {/*

write your code here

*/}

/function signature ends

Solution:

if (x,y outside maze) return false

if (x,y is goal) return true

if (x,y not open) return false

mark x,y as part of solution path

if (FIND-PATH(North of x,y) == true) return true

if (FIND-PATH(East of x,y) == true) return true

if (FIND-PATH(South of x,y) == true) return true

if (FIND-PATH(West of x,y) == true) return true

unmark x,y as part of solution path

return false*/

 

public boolean findPath(int x, int y){

// check x,y are outside maze.

if(x < 0 || x >= mazelength || y < 0 || y >= mazelength ){

return false;

}

if(maze[x][y] == 9) {

return true;

}

if(maze[x][y] != 1) return false;

//mark x, y as part of the solution path

if(maze[x][y] == 1){

maze[x][y] = 3;

}

// move North

if( findPath(x-1,y)){

return true;

}

//move East

if( findPath(x,y+1)) return true;

//move South

if( findPath(x+1,y)) return true;

//move West

if( findPath(x,y-1)) return true;

// unMark x,y as part of the solution. maze[x][y] = 0;

return false;

}

public void printSolution(){ System.out.println("Final Solution ::::::: "); for(int i=0;i<mazelength;i++){

for(int j=0;j<mazelength;j++){ System.out.print(" "+maze[i][j]+" ");

}

System.out.println();

}

}

public static void main(String args[]){

 

RatMazeProblem ratMazeProblem = new RatMazeProblem();

System.out.println(" is Path exist ::: "+ratMazeProblem.findPath(0,0));

ratMazeProblem.printSolution();

}

}