Java AC 11ms DFS Beats 97% With Comments - Easy to Understand


  • 2
    S
    public class Solution {
        public boolean hasPath(int[][] maze, int[] start, int[] destination) {
            if (maze == null || maze.length == 0) return false;
            
            boolean[][] visited = new boolean[maze.length][maze[0].length];
            return dfs(maze, start, visited, destination);
        }
        
        private boolean dfs(int[][] maze, int[] start, boolean[][] visited, int[] destination) {
            if (start[0] == destination[0] && start[1] == destination[1]) return true;
            if (visited[start[0]][start[1]]) return false;
            
            visited[start[0]][start[1]] = true;
            
            for (int i = 0; i < 4; ++i) {//roll to four directions: 0 for up, 1 for down, 2 for left, 3 for right
                int[] next = rolling(start, maze, i);
                if (dfs(maze, next, visited, destination)) {
                    return true;
                }
            }
            
            return false;
        }
        
        private int[] rolling(int[] start, int[][] maze, int dir) {
            int row = start[0], col = start[1];
            
            if (dir == 0 || dir == 1) { //up and down
                while (dir == 0 ? row - 1 >= 0 && maze[row - 1][col] == 0 : row + 1 < maze.length && maze[row + 1][col] == 0) {
                    row = dir == 0 ? row - 1 : row + 1;
                }
            }
            else if (dir == 2 || dir == 3) { //left and right
                while (dir == 2 ? col - 1 >= 0 && maze[row][col - 1] == 0 : col + 1 < maze[0].length && maze[row][col + 1] == 0) {
                    col = dir == 2 ? col - 1 : col + 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.