Similar to The Maze. Easy-understanding Java bfs solution.


  • 25
    C

    Solution of The Maze: https://discuss.leetcode.com/topic/77471/easy-understanding-java-bfs-solution
    Solution of The Maze III: https://discuss.leetcode.com/topic/77474/similar-to-the-maze-ii-easy-understanding-java-bfs-solution

    We need to use PriorityQueue instead of standard queue, and record the minimal length of each point.

    public class Solution {
        class Point {
            int x,y,l;
            public Point(int _x, int _y, int _l) {x=_x;y=_y;l=_l;}
        }
        public int shortestDistance(int[][] maze, int[] start, int[] destination) {
            int m=maze.length, n=maze[0].length;
            int[][] length=new int[m][n]; // record length
            for (int i=0;i<m*n;i++) length[i/n][i%n]=Integer.MAX_VALUE;
            int[][] dir=new int[][] {{-1,0},{0,1},{1,0},{0,-1}};
            PriorityQueue<Point> list=new PriorityQueue<>((o1,o2)->o1.l-o2.l); // using priority queue
            list.offer(new Point(start[0], start[1], 0));
            while (!list.isEmpty()) {
                Point p=list.poll();
                if (length[p.x][p.y]<=p.l) continue; // if we have already found a route shorter
                length[p.x][p.y]=p.l;
                for (int i=0;i<4;i++) {
                    int xx=p.x, yy=p.y, l=p.l;
                    while (xx>=0 && xx<m && yy>=0 && yy<n && maze[xx][yy]==0) {
                        xx+=dir[i][0];
                        yy+=dir[i][1];
                        l++;
                    }
                    xx-=dir[i][0];
                    yy-=dir[i][1];
                    l--;
                    list.offer(new Point(xx, yy, l));
                }
            }
            return length[destination[0]][destination[1]]==Integer.MAX_VALUE?-1:length[destination[0]][destination[1]];
        }
    }
    

    Modified 2017/3/27:
    Why using PriorityQueue?

    We can consider this question as a shortest-route graph problem, that is, each stoppable point is a vertical, where every possible path between two nodes is an edge.
    In this way, we can using Dijkstra algorithm to solve this problem, and that's why we use PriorityQueue.


  • 18
    A

    why using the PriorityQueue? I think queue is enough.


  • 0
    H
    This post is deleted!

  • 0
    H

    Nice Solution!


  • 11
    G
    // thanks for sharing! very inspiring!
    // changed a little bit of your code and improve the runtime to about 20ms
    public static final int[][] dirs = new int[][] {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    
    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        if(maze == null || maze.length == 0 || maze[0].length == 0) {
            return -1;
        }
    
        int m = maze.length;
        int n = maze[0].length;
        int[][] dp = new int[m][n];
        Queue<Pair> que = new LinkedList<>();
    
        que.offer(new Pair(start[0], start[1], 0));
        for(int i = 0; i < m; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
    
    
        while(!que.isEmpty()) {
            Pair cur = que.poll();
            for(int[] dir : dirs) {
                int nextX = cur.x;
                int nextY = cur.y;
                int len = cur.len;
                while(nextX < m && nextX >= 0 && nextY < n && nextY >= 0 && maze[nextX][nextY] == 0) {
                    nextX += dir[0];
                    nextY += dir[1];
                    len++;
    
                }
                nextX -= dir[0];
                nextY -= dir[1];
                len--;
    
                // avoid going through unneccessary cases.
                if(len > dp[destination[0]][destination[1]]) {
                    continue;
                }
    
                if(len < dp[nextX][nextY]) {
                    dp[nextX][nextY] = len;
                    que.offer(new Pair(nextX, nextY, len));
                }
            }
        }
    
        return dp[destination[0]][destination[1]] == Integer.MAX_VALUE ? -1 : dp[destination[0]][destination[1]];
    }
    
    class Pair {
        int x;
        int y;
        int len;
        public Pair(int x, int y, int len) {
            this.x = x;
            this.y = y;
            this.len = len;
        }
    }

  • 1
    C

    @GaoLiaoLiao Thank you! This is the best solution to the question I've ever read.


  • 1
    M

    @ckcz123

    Great solution! Thanks for sharing!
    not sure how your co-workers review your code, but when I look at your code, feel @_@


  • 1
    P

    I think since we already save each node's minimum length in extra matrix, we don't need to save each node's length as a pair into the queue.


  • 1

    @aaaeeeo Yes, you are right. There is no need to use PriorityQueue because all the reflection nodes need to be visited anyway. The order doesn't affect since we will check the length[i][j] with the node.l


  • 0
    Z

    @YingLL I think the solution here maybe not efficient enough, think about it this way.

    If we don't record the length, but use a map to store the current minimum distance to reach a particular point, then if we have found a solution already and the top element in the priority queue is larger than our current minimum result, we don't need to go through the rest of the points.


  • 0
    M

    @aaaeeeo I think this is like a modified Dijkstra's algorithm, think of every stoppable point as a node and every possible path between two nodes as a edge.


  • 0

    @zhongyuan9817 I understand that you are trying to use a map to store the current minimum distance to a particular point. That's also what the 2D array of length[m][n] does because length[i][j] stores the min distance to point[i][j]. I think it's the same thing.

    Followed your idea, I re-submitted several different versions of code. But they are still using array length[][]:

    1. priority queue version, which is the original post
    2. priority queue with comparison, which is your idea. I added this statement in the while loop. It's right after the statement "length[p.x][p.y]=p.l;":
    if (length[destination[0]][destination[1]] != Integer.MAX_VALUE && length[p.x][p.y] > length[destination[0]][destination[1]]) {
            return length[destination[0]][destination[1]];
    }
    

    "length[destination[0]][destination[1]" is a distance from the start point to the destination.
    "p" is the element that is polled from the priority queue (I think that's the "top element" that you was saying).
    Basically it means if there is already a solution, compare the current distance value with the top element in the priority queue. If the distance is smaller that the element from priority queue, we will return the result without visiting the rest of the points.

    1. normal queue version.

    It seems that #2 is a little bit faster than #1 since there is an additional judgment that will return the result directly.
    But both #1 and #2 are obviously slower than #3. I guess that's because when you use priority queue, every time when you modify the queue, it will cost more time than a normal queue.


  • 0

    Thanks for sharing.
    I want to ensure I understand the using of PriorityQueue correctly. By using PriorityQueue, we can first solve the path with smaller current length, thus we can come to the final solution earlier.
    Is it right?


  • 1
    C

    @aaaeeeo @YingLL @Tōsaka-Rin I have modified my post to answer the question Why using PriorityQueue?


  • 0

    @ckcz123 Yes! It makes sense when you bring out Dijkstra algorithm. Thanks! But I'm still curious why using priority queue is slower than using normal queue. Or is it just me getting this result?


  • 1

    @GaoLiaoLiao, We don't need to use a priority queue here. Priority queues are implemented based on min-heaps (or max-heaps) and dequeuing from them is equivalent to extract-min (or extract max) which is O(lg n)-time.

    BFS can also calculate shortest paths in unweighted graphs. Here, we can come up with a solution using BFS and regular queues.


  • 1

    I think you can terminate early if found the destination polled from PriorityQueue.
    Cause the ball can only roll vertically or horizontally, the first encountered destination must be shortest.


  • 3
    F

    @ckcz123 if you want to use priority queue to always pop shortest path node, you also need use visited mark for preventing visited node going into queue again.

    I rewrite following codes;

              // bfs, like-dijikstra
        static int[][] dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};
        public int shortestDistance(int[][] maze, int[] start, int[] destination) {
            if (maze.length == 0 || maze[0].length == 0) return -1;
            int m = maze.length, n = maze[0].length;
            int[][] dist = new int[m][n];
            boolean[][] visited = new boolean[m][n];
            
            PriorityQueue<int[]> queue = new PriorityQueue<>(m, (i1,i2)->{
                return i1[2]-i2[2];
            });
            queue.offer(new int[]{start[0], start[1], 0});
            while (!queue.isEmpty()) {
                int[] node = queue.poll();
                if (visited[node[0]][node[1]]) continue;
                if (node[0] == destination[0] && node[1] == destination[1]) return node[2];
                visited[node[0]][node[1]] = true;
    
                for (int[] dir: dirs) {
                    int x = node[0];
                    int y = node[1];
                    int step = node[2];
                    while (x+dir[0] >= 0 && x+dir[0] < m && y+dir[1] >= 0 && y+dir[1] < n && maze[x+dir[0]][y+dir[1]] != 1) {
                        x += dir[0];
                        y += dir[1];
                        step++;
                    }
                    if (visited[x][y]) continue;
                    if (dist[x][y] == 0 || dist[x][y] > step) {
                        dist[x][y] = step;
                        queue.offer(new int[]{x,y,step});
                    }
                }
            }
            return -1;
        }

  • 0
    D

    @aaaeeeo so, queue is still ok. But Priority Queue is batter. It's an optimization inspired by Dijsktra algorithm.


  • 0
    T

    I modified your solution:

    public class Solution {
        
        class point{
            int x;
            int y;
            int distance;
            point(int x,int y,int z){
                this.x=x;
                this.y=y;
                this.distance=z;
            }
        }
         
        public int shortestDistance(int[][] maze, int[] start, int[] destination) {
              int[][] dis = new int[maze.length][maze[0].length];
              for(int i=0;i<maze.length;i++){
                  Arrays.fill(dis[i],Integer.MAX_VALUE);
              }
              PriorityQueue<point> pq = new PriorityQueue<>(1,new Comparator<point>(){
                     public int compare(point a,point b){
                          return a.distance-b.distance;
                     }
              });     
              
              pq.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(!pq.isEmpty()){
                  point t=pq.poll();
                  
                  for(int[] dir:dirs){
                      int i=t.x+dir[0];
                      int j=t.y+dir[1];
                      if(i<0||i>=maze.length||j<0||j>=maze[0].length||maze[i][j]==1) continue;
                      
                      if(dir[1]!=0){
                          while(j>0&&j<maze[0].length-1&&maze[i][j+dir[1]]==0){
                              j+=dir[1];
                          }
                          
                          int r=t.distance+Math.abs(j-t.y);
                          if(dis[i][j]>r){
                              dis[i][j]=r;
                              pq.offer(new point(i,j,r));
                          }
                      }else if(dir[0]!=0){
                          while(i>0&&i<maze.length-1&&maze[i+dir[0]][j]==0){
                              i+=dir[0];
                          }
                          int r=t.distance+Math.abs(i-t.x);
                          if(dis[i][j]>r){
                              dis[i][j]=r;
                              pq.offer(new point(i,j,r));
                          }
                      }
                  }
              }
              
            int res=dis[destination[0]][destination[1]];
            return res==Integer.MAX_VALUE ? -1:res;
        }
    }
    
    

Log in to reply
 

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