# 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

'''
package com.mywork.amazon;

public class RatMazeProblem {

`````` int maze[][] = {{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}
};
int mazelength = maze.length;
// This program considers RAT can move all four directions.
``````

/* FIND-PATH(x, y)

``````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();

}
``````

}
'''

• We have to perform DFS. Space Complexity will be O(N2) -> STACK. I am confused with time complexity here. I suppose it has to be O(N2) since at any point of time at max I will be exploring the whole maze.

Correct me if I am wrong?

``````package Amazon;

public class MazeCheeseReachable {

private boolean isPath(int[][] matrix, int ROWS, int COLS, int row, int col) {
if(matrix[row][col] == 9){
return true;
}

// visit this path
matrix[row][col] = 2;
boolean exist = false;

// right
if(!exist && col+ 1 < COLS && (matrix[row][col+1] == 1 || matrix[row][col+1] == 9)) {
exist = isPath(matrix, ROWS, COLS, row, col+1);
}

// down
if(!exist && row+1 < ROWS && (matrix[row+1][col] == 1 || matrix[row+1][col] == 9)) {
exist = isPath(matrix, ROWS, COLS, row+1, col);
}

// left
if(!exist && col-1 >=0 && (matrix[row][col-1] == 1 || matrix[row][col-1] == 9)) {
exist = isPath(matrix, ROWS, COLS, row, col-1);
}

// top
if(!exist && row-1 >=0 && (matrix[row-1][col] == 1 || matrix[row-1][col] == 9)) {
exist = isPath(matrix, ROWS, COLS, row-1, col);
}

// un-visit this path
matrix[row][col] = 1;
return exist;
}

public static void main(String[] args) {
MazeCheeseReachable mcr = new MazeCheeseReachable();

int matrix[][] = {{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}};

System.out.println(mcr.isPath(matrix, matrix.length, matrix[0].length, 0, 0));
}

}

``````

• I think it is important to memorize the visited cells here.

``````public class RatInMaze {

public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] maze = {{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}};
HashSet<String> invalidSet = new HashSet<> ();
boolean flg = isPath(maze, 0, 0, invalidSet);
if(flg) System.out.println("Yes");
else System.out.println("No");

}

public static boolean isPath(int[][] arr, int x, int y, HashSet<String> invalidSet){
if(x<0||x>arr.length-1||y<0||y>arr[x].length-1){
return false;
}
if(arr[x][y]==0){
return false;
}
if(arr[x][y]==9){
return true;
}
if(arr[x][y]==1 && !invalidSet.contains(x+" "+y)){
return isPath(arr,x-1,y,invalidSet)||isPath(arr,x+1,y,invalidSet)
||isPath(arr,x,y-1,invalidSet)||isPath(arr,x,y+1,invalidSet);
}
return false;
}
}

``````

• @arjun033 I agree about the memoization but we can perform memoization directly on the board by marking each visited cell (I've used -1 here). This works since DFS implies that all reachable paths through a position would already have been explored when we're done with that cell so we can just leave the markings. This will allow us to memoize using no additional space. If the input maze is immutable however, the only option would be to use external space.

``````def dfs(r, c, maze, moves):
if r < 0 or r >= len(maze) or c < 0 or c >= len(maze[0]) or maze[r][c] <= 0: return False
if maze[r][c] == 9: return True # cheese found
maze[r][c] = -1
for dr, dc in moves:
r_, c_ = r + dr, c + dc
if dfs(r_, c_, maze, moves): return True
return False

def reachable(maze):
# r, c moves. i.e. (0, 1) -> 1 col to the right
moves = {(0, 1), (0, -1), (1, 0), (-1, 0)}
# 1 is path 0 is wall
return dfs(0, 0, maze, moves)
``````

• @Ellest Absolutely right! I just did not want to tinker with the original array :D

• @ramanpreetSinghKhinda I think this code looks simple instead of four separate if statements.

for (int i = -1 ; i <= 1 ; i++)
for (int j = -1 ; j <= 1; j++)
if !( row == 0 && col == 0) {
int row = row + i;
int col = col + j
if (!exist && row + i < ROWS && col + j < COLS && (matrix[row][col] == 1 || matrix[row][col]) }
............
..........

......

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.