The Maze


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.row1,src.col),dest,visited)  traverse(maze,new Coordibate(src.row+1,src.col),dest,visited)  traverse(maze,new Coordibate(src.row,src.col1),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...

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

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

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