Java BFS and DFS AC solution with detailed explanation


  • 0
    M

    General idea:
    Similar as the previous two maze problem, we can define a Point with x, y, d and path direction.
    In order to compare the distance from start point and also the lexicographically order of Point’s direction, we can implement Comparable in the Point class.
    For each point, it carries its path from start point to it.
    Within the searching new points process, if we find a hole that means, we can hit the hole. We cannot stop, we need to continue to run until we accessed all possibilities.
    Idea came from https://discuss.leetcode.com/topic/77474/similar-to-the-maze-ii-easy-understanding-java-bfs-solution

    Method 1: BFS,

    Time = O(nm log(nm)), one point at most goes into and out minheap once;
    Space = O(n^2 m^2), since each point may carry one path, the longest path is O(nm), there are totally nm points, so total space will be O((nm)^2).

    code is in the below.

    Method 2: DFS, Time = O(mn), Space = O(mn).
    Since each point only accessed once, so the time and space complexity is the size of matrix. This analysis may be wrong since DFS time is much slower than BFS. Please let me know if you figure out the error, thanks!

    class Solution {
        static class Point implements Comparable<Point> {
            int x;
            int y;
            int d = Integer.MAX_VALUE;
            String s = "";
            
            Point(int x, int y) {
                this.x = x;
                this.y = y;
            }
            
            Point(int x, int y, int d, String next) {
                this.x = x;
                this.y = y;
                this.d = d;
                this.s += next;
            }
            
            public int compareTo(Point p) {
                if (this.d == p.d) {
                    return this.s.compareTo(p.s);
                }
                return this.d < p.d ? -1 : 1;
            }
        }
    
        // BFS;
        public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
            int m = maze.length, n = maze[0].length;
            Point[][] points = new Point[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    points[i][j] = new Point(i, j);
                }
            }
            PriorityQueue<Point> minheap = new PriorityQueue<>();
            int[][] dirs = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
            String[] move = new String[] {"u", "d", "l", "r"};
            // 1. initialize
            Point start = points[ball[0]][ball[1]];
            start.d = 0;
            minheap.offer(start);
            while (!minheap.isEmpty()) {
                Point cur = minheap.poll();
                // expand four directions;
                for (int i = 0; i < dirs.length; i++) {
                    int[] dir = dirs[i];
                    String nextMove = move[i];
                    Point newPoint = findNewPointWithPath(maze, hole, dir, nextMove, cur);
                    // we should run all positions to get the shortest one!
                    // if (newPoint.x == hole[0] && newPoint.y == hole[1]) {
                    //     return newPoint.s;
                    // }
                    if (points[newPoint.x][newPoint.y].compareTo(newPoint) > 0) {
                        points[newPoint.x][newPoint.y] = newPoint;
                        minheap.offer(newPoint);
                    }
                }
            }
            return points[hole[0]][hole[1]].d == Integer.MAX_VALUE ? "impossible" : points[hole[0]][hole[1]].s;
        }
    
        private Point findNewPointWithPath(int[][] maze, int[] hole, int[] dir, String nextMove, Point cur) {
            int m = maze.length, n = maze[0].length;
            int x = cur.x, y = cur.y, d = cur.d;
            String s = cur.s + nextMove;
            boolean hitHole = false;
            // 1. hit the wall; if there is a hole in the path, break;
            while (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == 0) {
                if (x == hole[0] && y == hole[1]) {
                    hitHole = true;
                    break;
                }
                x += dir[0];
                y += dir[1];
                d++;
            }
            // 1.1 check whehter hit the hole or not;
            if (hitHole) {
                return new Point(x, y, d, s);
            }
            // 2. one step back
            x -= dir[0];
            y -= dir[1];
            d--;
            return new Point(x, y, d, s);
        }
    
        // DFS
        public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
            int m = maze.length, n = maze[0].length;
            Point[][] points = new Point[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    points[i][j] = new Point(i, j);
                }
            }
            int[][] dirs = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
            String[] move = new String[] {"u", "d", "l", "r"};
            Point start = points[ball[0]][ball[1]];
            start.d = 0;
            dfs(maze, start, hole, dirs, move, points);
            return points[hole[0]][hole[1]].d == Integer.MAX_VALUE ? "impossible" : points[hole[0]][hole[1]].s;
        }
        
        private void dfs(int[][] maze, Point cur, int[] hole, int[][] dirs, String[] move, Point[][] points) {
            if (cur.compareTo(points[cur.x][cur.y]) > 0) {
                return;
            }       
            points[cur.x][cur.y] = cur;
            for (int i = 0; i < dirs.length; i++) {
                Point newPoint = findNewPointWithPath(maze, hole, dirs[i], move[i], cur);
                dfs(maze, newPoint, hole, dirs, move, points);
            }
        }
    }
    

Log in to reply
 

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