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.


Log in to reply
 

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