Is cheese reachable in the maze?
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 o 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,0.
Write a method isPath of class Maze Path to determine if Mooshak can reach the huge chunk of cheese. The input to isPath consists of a two dimensional array grid 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/
Example 8x8 maze where Mooshak can get the cheese.
1 0 1 1 1 0 0 1
1 0 0 0 1 1 1 1
1 0 0 0 0 0 0 0
1 0 1 0 9 0 1 1
1 1 1 0 1 0 0 1
1 0 1 0 1 1 0 1
1 0 0 0 0 1 0 1
1 1 1 1 1 1 1 1
/**
/**
* Created by LEI_D on 6/13/2017.
*/
import java.util.Set;
import java.util.HashSet;
public class RatInMaze {
int[] drow = new int[]{-1,1,0,0};
int[] dcol = new int[]{0,0,-1,1};
public boolean isReachable(int[][] maze) {
if (maze == null || maze.length == 0) {
return false;
}
boolean[][] visited = new boolean[maze.length][maze[0].length];
return isPath(maze, 0,0,visited);
}
private boolean isPath(int[][] maze, int row, int col, boolean[][] visited) {
if (row < 0 || row >= maze.length || col < 0 || col >= maze[0].length) {
return false;
}
if(maze[row][col] == 0) {
visited[row][col] = true;
return false;
}
if(maze[row][col] == 9) {
visited[row][col] = true;
return true;
}
if (maze[row][col] == 1 && !visited[row][col]) {
visited[row][col] = true;
return isPath(maze, row+1, col, visited) || isPath(maze,row - 1, col, visited) || isPath(maze, row, col - 1, visited)
|| isPath(maze, row, col + 1, visited);
}
return false;
}
}