Is cheese reachable in the maze?


  • 1
    L

    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


  • 0
    H

    Refer Link: https://www.cs.bu.edu/teaching/alg/maze/
    '''
    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();
    	
    	 
    }
    

    }
    '''


  • 2

    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));
    	}
    
    }
    
    

  • 0
    A

    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){
    			invalidSet.add(x+" "+y);
    			return false;
    		}
    		if(arr[x][y]==0){
    			invalidSet.add(x+" "+y);
    			return false;
    		}
    		if(arr[x][y]==9){
    			return true;
    		}
    		if(arr[x][y]==1 && !invalidSet.contains(x+" "+y)){
    			invalidSet.add(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;
    	}
    }
    
    

  • 0

    @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)
    

  • 0
    A

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


Log in to reply
 

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