AC backtracking solution


  • 0
    R
    class Solution {
        public boolean hasPath(int[][] maze, int[] start, int[] destination) {
            
            int[][] dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}};
            boolean[][] visited = new boolean[maze.length][maze[0].length];
            boolean[][] failed = new boolean[maze.length][maze[0].length];
    
            visited[start[0]][start[1]] = true;
    
            return move(maze, start, destination, dirs, visited, failed);
        }
        
        public boolean move(int[][] maze, int[] curPos, int[] destination, int[][] dirs, boolean[][] visited, boolean[][] failed) {
            if(failed[curPos[0]][curPos[1]]) return false;
            
            if(curPos[0] == destination[0] && curPos[1] == destination[1])  return true;
            
            for(int[] eachDir : dirs) {
                int[] nextPos = moveToWall(curPos, eachDir, maze);
                if(!visited[nextPos[0]][nextPos[1]]) {
                    visited[nextPos[0]][nextPos[1]] = true;
                    if(move(maze, nextPos, destination, dirs, visited, failed)) return true;
                    visited[nextPos[0]][nextPos[1]] = false;
                }
            }
            failed[curPos[0]][curPos[1]] = true;
            return false;
        }
        
        public int[] moveToWall(int[] curPos, int[] dir, int[][] maze) {
            int row = curPos[0];
            int col = curPos[1];
            while(row + dir[0] >= 0 && 
                  row + dir[0] < maze.length &&
                  col + dir[1] >= 0 && 
                  col + dir[1] < maze[0].length &&
                  maze[row + dir[0]][col + dir[1]] != 1) {
                row = row + dir[0];
                col = col + dir[1];
            }
            return new int[]{row, col};
        }
        
    }
    

Log in to reply
 

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