Simple Java DFS with comments


  • 16
    • Search in the four possible directions when coming to a stopping point (i.e. a new starting point).
    • Keep track of places that you already started at in case you roll back to that point.
    public class Solution {
        public boolean hasPath(int[][] maze, int[] start, int[] destination) {
            boolean[][] startedHere = new boolean[maze.length][maze[0].length]; // mark visited starting points
            return dfs(maze, startedHere, start, destination);
        }
        
        private boolean dfs(int[][] maze, boolean[][] startedHere, int[] start, int[] destination) {
            if (startedHere[start[0]][start[1]]) return false;
            if (Arrays.equals(start, destination)) return true;
            
            startedHere[start[0]][start[1]] = true; // in case we roll back to a point we already started at
            
            BiPredicate<Integer, Integer> roll = (rowInc, colInc) -> {
                int row = start[0], col = start[1]; // init new start row and col
                while (canRoll(maze, row + rowInc, col + colInc)) {
                    row += rowInc;
                    col += colInc;
                }
                return dfs(maze, startedHere, new int[]{row, col}, destination); // pass in new start to dfs
            };
            
            if (roll.test(1, 0)) return true; // roll up
            if (roll.test(0, 1)) return true; // roll right
            if (roll.test(-1, 0)) return true; // roll down
            if (roll.test(0, -1)) return true; // roll left
            
            return false; // return false if no paths led to destination
        }
        
        private boolean canRoll(int[][] maze, int row, int col) {
            if (row >= maze.length || row < 0 || col >= maze[0].length || col < 0) return false; // stop at borders
            return maze[row][col] != 1; // stop at walls (1 -> wall)
        }
    }
    

    UPDATE: Also including one without using BiPredicate on every recursive call since it runs faster

    public class Solution {
        
        private static final int[] DIRECTIONS = { 0, 1, 0, -1, 0 };
        
        public boolean hasPath(int[][] maze, int[] start, int[] destination) {
            boolean[][] startedHere = new boolean[maze.length][maze[0].length];
            return dfs(maze, startedHere, start, destination);
        }
        
        private boolean dfs(int[][] maze, boolean[][] startedHere, int[] start, int[] destination) {
            if (startedHere[start[0]][start[1]]) return false;
            if (Arrays.equals(start, destination)) return true;
            
            startedHere[start[0]][start[1]] = true;
            
            for (int i = 0; i < DIRECTIONS.length - 1; i++) {
                int[] newStart = roll(maze, start[0], start[1], DIRECTIONS[i], DIRECTIONS[i + 1]);
                if (dfs(maze, startedHere, newStart, destination)) return true;
            }
            
            return false;
        }
        
        private int[] roll(int[][] maze, int row, int col, int rowInc, int colInc) {
            while (canRoll(maze, row + rowInc, col + colInc)) {
                row += rowInc;
                col += colInc;
            }
            
            return new int[]{row, col};
        }
        
        private boolean canRoll(int[][] maze, int row, int col) {
            if (row >= maze.length || row < 0 || col >= maze[0].length || col < 0) return false;
            return maze[row][col] != 1; // 1 is a wall
        }
    }
    

  • 1
    S

    @KidOptimo Nice one, I liked the BiPredicate approach - I rarely see some java-8 out there.

    Note though that your first check in dfs could be simplified with Arrays.equals(start, destination).


  • 0

    @savardjf Good call, thanks! Updated


  • 0
    Y

    Can anyone implement this idea in Maze II ?


  • 0

    @Yan_Sylvia_Liu

    Tried that when i first attempted Maze II but I got TLE because you have to make sure that you find the shortest path and not just any path. So BFS is more suited for Maze II.


  • 2
    S

    Same idea:

    int[][] dirs = new int[][]{ {-1, 0}, {1, 0}, {0, 1}, {0, -1} };
        
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        boolean[][] visited = new boolean[maze.length][maze[0].length];
        return dfs(maze, start, destination, visited);
    }
    
    private boolean dfs(int[][] maze, int[] p, int[] destination, boolean[][] visited) {
        if (visited[p[0]][p[1]]) {
            return false;
        }
        if (p[0] == destination[0] && p[1] == destination[1]) {
            return true;
        }
        visited[p[0]][p[1]] = true;
        for (int i = 0; i < dirs.length; i++) {
            int[] d = dirs[i];
            int row = p[0];
            int col = p[1];
            while (isValid(maze, row + d[0], col + d[1])) {
                row += d[0];
                col += d[1];
            }
            if (dfs(maze, new int[]{ row, col }, destination, visited)) {
                return true;
            }
        }
        return false;
    }
    
    private boolean isValid(int[][] maze, int row, int col) {
        return row >= 0 && row < maze.length && col >= 0 && col < maze[0].length && maze[row][col] != 1;
    }
    

  • 0
    Z

    Thank you for the solution! I rewrote it in C++. It seems BFS is faster than DFS, although DFS should be faster for whether it is feasible problem.

    class Solution {
    public:
        bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
            int m = maze.size(), n = maze[0].size();
            vector<vector<int>> visited(m, vector<int>(n, 0));
            return dfs(maze, visited, start[0], start[1], destination);
        }
    private:
        bool dfs(vector<vector<int>>& maze, vector<vector<int>>& visited, int row, int col, vector<int>& des) {
            int m = maze.size(), n = maze[0].size();
            if (visited[row][col]) return false;
            visited[row][col] = 1;
            if (row == des[0] && col == des[1]) return true;
            vector<int> d1({0, 1, 0, -1}), d2({1, 0, -1, 0});
            for (int i = 0; i < 4; ++i) {
                int r = row + d1[i], c = col+d2[i];
                while (r >= 0 && r< m && c >= 0 && c < n && maze[r][c] == 0) {
                    r += d1[i];
                    c += d2[i];
                }
                r -= d1[i];
                c -= d2[i];
                if (dfs(maze, visited, r, c, des)) return true;
            }
            return false;
        }
    };
    

  • 0

  • 0
    F

    Same idea.

    class Solution {
        public boolean hasPath(int[][] maze, int[] start, int[] destination) {
            int m = maze.length, n = maze[0].length;
            boolean[][] visited = new boolean[m][n];
            return helper(maze, start, destination, visited);
        }
        public boolean helper(int[][] maze, int[] start, int[] destination, boolean[][] visited) {
            if (start[0] < 0 || start[0] >= maze.length || start[1] < 0 || start[1] >= maze[0].length || 
                visited[start[0]][start[1]]) {
                return false;
            }
            visited[start[0]][start[1]] = true;
            if (start[0] == destination[0] && start[1] == destination[1]) {
                return true;
            }
            int[][] dir = new int[][]{{1, -1, 0, 0}, {0, 0, 1, -1}};
            for (int i = 0; i < 4; i++) {
                    int row = start[0];
                    int col = start[1];
                    while (row >= 0 && row < maze.length && col >= 0 && col < maze[0].length && maze[row][col] != 1) {
                        row += dir[0][i];
                        col += dir[1][i];
                    }
                    row -= dir[0][i];
                    col -= dir[1][i];
                    if (helper(maze, new int[]{row, col}, destination, visited)) {
                        return true;
                    }
                }
            return false;
        }
    }
    

  • 0
    This post is deleted!

Log in to reply
 

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