A slightly different Java dfs solution, well commented


  • 0

    and I'm always wondering which one would be a better practice to create inter-methods access for variables that are needed during recursion, or by other methods, variables like visited, grid, matrix and whatever that commonly seen with dfs. to pass them explicitly through method call, or create class-wise reference like what I did here?

    any thoughts and discussions are appreciated and welcomed. thanks.

    class Solution {
        // directions the ball can rolling to: North, East, South, West, and Any (directions)
        // also corresponding to the offset in DIR
        private static final int N = 0, E = 1, S = 2, W = 3, A = 4;
        // direction offset with which the indices of the next move is generated
        private static final int[][] DIR = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        // boolean stop indicator that marks all the cells where the ball can stop
        private boolean[][] stop;
        // create references for class-wise access
        private int rowLen, colLen;
        private int[][] maze;
        private int[] destination;
    
        public boolean hasPath(int[][] maze, int[] start, int[] destination) {
            rowLen = maze.length;
            colLen = maze[0].length;
            this.maze = maze;
            this.stop = new boolean[rowLen][colLen];
            this.destination = destination;
            // mark the start point and start rolling to any directions
            stop[start[0]][start[1]] = true;
            return dfs(start[0], start[1], A);
        }
    
        private boolean dfs(int i, int j, int direction) {
            if (direction == A) {
                // proceed to the next move on all the four directions
                return dfs(i + DIR[N][0], j + DIR[N][1], N) ||
                        dfs(i + DIR[E][0], j + DIR[E][1], E) ||
                        dfs(i + DIR[S][0], j + DIR[S][1], S) ||
                        dfs(i + DIR[W][0], j + DIR[W][1], W);
            } else {
                // hit the boundary, or all, or some stop arrived previously
                if (hitTheBoundary(i, j) || maze[i][j] == 1 || stop[i][j]) {
                    return false;
                }
                // proceed to the next move indicated by the `direction`
                int row = i + DIR[direction][0], col = j + DIR[direction][1];
                if (hitTheBoundary(row, col) || maze[row][col] == 1) {
                    // arrived the destination, or keep rolling to any direction at this stop
                    stop[i][j] = true;
                    return i == destination[0] && j == destination[1] || dfs(i, j, A);
                } else {
                    // keep rolling to the previous direction
                    return dfs(row, col, direction);
                }
            }
        }
    
        private boolean hitTheBoundary(int i, int j) {
            return i < 0 || i >= rowLen || j < 0 || j >= colLen;
        }
    }
    

Log in to reply
 

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