Java BFS and DFS AC solution with detailed explanation


  • 0
    M

    Method 1: BFS2 by using PriorityQueue, Time = O(mn log(mn)), Space = O(mn).
    In order to find the shortest distance for the ball to stop at the destination, we need to use the PriorityQueue instead of queue to get the next start point.
    Idea came from: https://discuss.leetcode.com/topic/77472/similar-to-the-maze-easy-understanding-java-bfs-solution

    Initial condition: start place;
    Expand a new point: given current point <x, y, d>,
    next available point should be on four directions → next to the wall;
    Termination condition: hit the destination or no new elements.

    Instead of using visited[][] array, we use a distance[][] to denote the current distance from start point to current point.

    Initially, all points’ distance to start point is Integer.MAX_VALUE.

    Method 2: DFS, Time = O(mn), Space = O(mn).
    use DFS to traverse the whole array,
    use a distance[][] to store the distance from start point to current point, initially, all of them are Integer.MAX_VALUE;
    One position only be visited once.

    class Solution {
        static class Point {
            int x;
            int y;
            int d; // distance;
            Point(int x, int y, int d) {
                this.x = x;
                this.y = y;
                this.d = d;
            }
        }
        
        // 1. BFS;
        public int shortestDistance(int[][] maze, int[] start, int[] destination) {
            int m = maze.length, n = maze[0].length;
            int[][] dis = new int[m][n]; // distance from start point to current position;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    dis[i][j] = Integer.MAX_VALUE; // initialize;
                }
            }
            PriorityQueue<Point> minheap = new PriorityQueue<>(new Comparator<Point>() {
                @Override
                public int compare(Point p1, Point p2) {
                    if (p1.d == p2.d) {
                        return 0;
                    }
                    return p1.d < p2.d ? -1 : 1;
                }
            });
            // 1. initialize;
            minheap.offer(new Point(start[0], start[1], 0));
            dis[start[0]][start[1]] = 0;
            int[][] dirs = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
            while (!minheap.isEmpty()) {
                Point cur = minheap.poll();
                if (cur.x == destination[0] && cur.y == destination[1]) {
                    return cur.d;
                }
                // expand to four directions;
                for (int[] dir : dirs) {
                    Point newPoint = findNewPoint(maze, dir, cur);
                    if (dis[newPoint.x][newPoint.y] > cur.d) { // unvisited before!
                        dis[newPoint.x][newPoint.y] = newPoint.d;
                        minheap.offer(newPoint);
                    }
                }
            }
            return -1;
        }
        
        private Point findNewPoint(int[][] maze, int[] dir, Point cur) {
            int m = maze.length, n = maze[0].length;
            int x = cur.x, y = cur.y, d = cur.d;
            // 1. hit the wall;
            while (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == 0) {
                x += dir[0];
                y += dir[1];
                d++;
            }
            // 2. one step back;
            x -= dir[0];
            y -= dir[1];
            d--;
            return new Point(x, y, d);
        }
    
       // 2. DFS;
       public int shortestDistance(int[][] maze, int[] start, int[] destination) {
            int m = maze.length, n = maze[0].length;
            int[][] dis = new int[m][n]; // distance from start point to current position;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    dis[i][j] = Integer.MAX_VALUE; // initialize;
                }
            }
            int[][] dirs = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
            dfs(maze, new Point(start[0], start[1], 0), destination, dis, dirs);
            return dis[destination[0]][destination[1]] == Integer.MAX_VALUE ? -1 : dis[destination[0]][destination[1]];
        }
        
        private void dfs(int[][] maze, Point cur, int[] destination, int[][] dis, int[][] dirs) {
            if (cur.d >= dis[cur.x][cur.y]) {
                return;
            }
            dis[cur.x][cur.y] = cur.d;
            for (int[] dir : dirs) { // all four directions;
                Point newPoint = findNewPoint(maze, dir, cur);
                dfs(maze, newPoint, destination, dis, dirs);
            }
        }
    }
    

Log in to reply
 

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