Java BFS and DFS AC solution with detailed explanation


  • 0
    M

    General idea:
    Because the ball only can stop before wall, so we only need to check the points before wall.
    For each position, we try four directions to hit the wall, then back one step, which are the points just before wall. So we only need to put these points into the queue in BFS or visit these points in DFS.

    Method 1: BFS, Time = O(mn), Space = O(mn).
    Idea came from: https://discuss.leetcode.com/topic/77471/easy-understanding-java-bfs-solution
    Add each position into the queue, and search it.

    Method 2: DFS, Time = O(mn), Space = O(mn).

    class Solution {
        // 1. BFS;
        public boolean hasPath(int[][] maze, int[] start, int[] destination) {
            int m = maze.length, n = maze[0].length;
            boolean[][] visited = new boolean[m][n];
            Queue<int[]> queue = new LinkedList<>();
            queue.offer(start);
            visited[start[0]][start[1]] = true;
            int[][] dirs = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
            while (!queue.isEmpty()) {
                int[] cur = queue.poll();
                if (cur[0] == destination[0] && cur[1] == destination[1]) {
                    return true;
                }
                // try all directions to hit the wall, then one step back to find all positions just before wall.
                for (int[] dir : dirs) {
    		    int[] newStart = findNewStart(maze, dir, cur);
                    // check whether need to add into queue;
                    if (!visited[newStart[0]][newStart[1]]) {
                        queue.offer(newStart);
                        visited[newStart[0]][newStart[1]] = true;
                    }
                }
            }
            return false;
        }
        
        private int[] findNewStart(int[][] maze, int[] dir, int[] cur) {
            int m = maze.length, n = maze[0].length;
            int x = cur[0], y = cur[1];
            // 1a. hit the wall;
            while (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == 0) {
                    x += dir[0];
                    y += dir[1];
            }
            // 1b. one step back;
            x -= dir[0];
            y -= dir[1];
            return new int[] {x, y};
        }
    
        // 2. DFS;
        public boolean hasPath(int[][] maze, int[] start, int[] destination) {
            int m = maze.length, n = maze[0].length;
            boolean[][] visited = new boolean[m][n];
            return dfs(maze, start, destination, visited);
        }
        
        private boolean dfs(int[][] maze, int[] start, int[] destination, boolean[][] visited) {
            if (visited[start[0]][start[1]]) {
                return false;
            }
            if (start[0] == destination[0] && start[1] == destination[1]) {
                return true;
            }
            visited[start[0]][start[1]] = true;
            
            // 1. find four directions possible start point which are points just before wall;
            int[][] dirs = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
            for (int[] dir : dirs) {
                int[] newStart = findNewStart(maze, dir, start);
                // use it as new start point to search
                if (dfs(maze, newStart, destination, visited)) {
                    return true;
                }
            }
            return false;
        }
    }
    

Log in to reply
 

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