The Maze


  • 1

    Click here to see the full article post


  • 0
    D

    Have tried doing this problem by backtracking method. Java solution below :

    class Coordibate
    {
        int row,col;
        public  Coordibate(int row,int col)
        {
            this.row = row;
            this.col = col;
        }
    
    }
    public class Maze {
    
        public static boolean traverse(int maze[][],Coordibate src,Coordibate dest,boolean visited[][])
        {
            if(src.row == maze.length || src.col == maze.length || src.row == -1 || src.col == -1 ) return false;
            if(maze[src.row][src.col] == 1 ) return false;
            if(visited[src.row][src.col] == true) return false;
            if(src.row == dest.row && src.col == dest.col)
            {
                System.out.print("found");
                return true;
            }
    
            visited[src.row][src.col] = true;
    
            return traverse(maze,new Coordibate(src.row-1,src.col),dest,visited) ||
                    traverse(maze,new Coordibate(src.row+1,src.col),dest,visited) ||
                    traverse(maze,new Coordibate(src.row,src.col-1),dest,visited) ||
                    traverse(maze,new Coordibate(src.row,src.col+1),dest,visited);
        }
    
        public static void main(String args[])
        {
            int maze [][] = {
                    {0,0,1,0,0},
                    {0,0,0,0,0},
                    {0,1,0,1,0},
                    {1,1,0,1,1},
                    {0,0,0,0,0}
            };
    
            boolean visited [][] = new boolean[maze.length][maze.length];
           for(int i=0;i<maze.length;i++)
           {
               for(int j=0;j<maze.length;j++)
                   visited[i][j] = false;
           }
    
            System.out.println(Maze.traverse(maze,new Coordibate(0,4),new Coordibate(4,4),visited));
    
        }
    

    Complexity of this solution should be O(mn).
    So, which approach is efficient - BFS or backtracking ? Or, both the approaches look similar ? Suggestions/Thoughts...


  • 0
    G

    Is this correct? It seems you are walking step by step, which is not true. You can walk more than one step along one direction as long as didn't reach the wall.


  • 0

    @guoleisun We aren't walking step by step. But, after every step we're trying to check if we've reached a wall. Only that end position is considered at last, which is just adjacent to the wall.


  • 1

    @devashish2008 DFS and your backtracking approach are very similar, both are using recursion. BFS and backtracking have same complexity but I think BFS would be more efficient as it is iterative while other one is recursive.


  • 0
    Y

    The time complexity analysis is should be O(mn(m+n)).
    Determining the position after a left/right movement is O(m), and O(n) after a up/down movement.


  • 0
    M

    @vinod23
    My dfs solution just got accepted.
    Share my code and comments:

    // dfs solution
    class Solution {
        private int[] dr;
        private int[] dc;
        private int[][] MAZE;
        private int R;
        private int C;
        private int[] dest;
        private boolean res;
        public boolean hasPath(int[][] maze, int[] start, int[] destination) {
            dr = new int[]{-1, 1, 0, 0}; // u d l r
            dc = new int[]{0, 0, -1, 1}; // u d l r
            MAZE = maze;
            R = maze.length;
            C = maze[0].length;
            dest = destination;
            res = false;
            
            // doesn't care the initial direction parameter
            dfs(-1, start, new boolean[R][C]);
            return res;
        }
        
        private void dfs(int dir, int[] start, boolean[][] visited) {
            int r = start[0], c = start[1];
            if (Arrays.equals(start, dest)) {
                res = true;
                return;
            } 
            if (visited[r][c]) return;
            visited[r][c] = true;
            // up down left right
            for (int i = 0; i < 4; ++i) {
                if (i == dir) continue; // skip the direction that will hit the wall again
                int x = r, y = c;
                while (isValid(new int[]{x + dr[i], y + dc[i]})) {
                    x += dr[i];
                    y += dc[i];
                }
                dfs(i, new int[]{x, y}, visited);
            }
        }
        
        // return true if the coord is valid and maze[coord] == 0;
        private boolean isValid(int[] coord) {
            int r = coord[0];
            int c = coord[1];
            if (r < 0 || r >= R || c < 0 || c >= C) return false; 
            if (MAZE[r][c] == 1) return false;
            return true;
        }
    }
    

Log in to reply
 

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