Java solution using priority search


  • 1
    X
    public class Solution {
        class Point{
            int x, y, l;
            public Point(int x, int y,int l){
                this.x = x;
                this.y = y;
                this.l = l;
            }
        }
        public int shortestDistance(int[][] maze, int[] start, int[] destination) {
            int m = maze.length, n = maze[0].length;
            int[][] visited = new int[m][n];
            PriorityQueue<Point> pq = new PriorityQueue<>((o1,o2)->(o1.l - o2.l));
            pq.offer(new Point(start[0], start[1], 0));
            int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
            while(!pq.isEmpty()){
                Point tmp = pq.poll();
                if(tmp.x == destination[0] && tmp.y == destination[1]) return tmp.l;
                if(tmp.l > visited[tmp.x][tmp.y]) continue;
                for(int[] dir : directions){
                    int tmpX = tmp.x, tmpY = tmp.y;
                    int cnt = 0;
                    while(tmpX + dir[0] >= 0 && tmpX + dir[0] < maze.length && tmpY + dir[1] >= 0 && tmpY + dir[1] < maze[0].length && maze[tmpX +  dir[0]][tmpY + dir[1]] == 0){
                        tmpX += dir[0];
                        tmpY += dir[1];
                        cnt++;
                    }
                    if(tmpX == start[0] && tmpY == start[1]) continue;
                    if(visited[tmpX][tmpY] == 0 || visited[tmpX][tmpY] > cnt + tmp.l){
                        visited[tmpX][tmpY] = cnt + tmp.l;
                        pq.offer(new Point(tmpX, tmpY, tmp.l + cnt));
                    }
                }
            }
            
            return -1;
        }
    }
    

Log in to reply
 

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