Java Solution using PriorityQueue


  • 0
    public class Solution {
        private PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>(){
        	@Override
        	public int compare(int[] o1, int[] o2) {
        		return o1[2] - o2[2];
        	}
        });
        
        public int shortestDistance(int[][] maze, int[] start, int[] destination) {
            queue.add(new int[]{start[0], start[1], 0});
            int m = maze.length, n = maze[0].length;
            int a, b;
            while(!queue.isEmpty()){
                int[] node = queue.poll();
                int i = node[0], j = node[1], d = node[2];
                maze[i][j] = 2;
                
                if(i == destination[0] && j == destination[1])
                    return d;
                
                a = i;
                while(a - 1 >= 0 && maze[a - 1][j] != 1)
                    a -= 1;
                if(maze[a][j] == 0)
                    queue.offer(new int[]{a, j, d + i - a});
                
                a = i;
                while(a + 1 < m && maze[a + 1][j] != 1)
                    a += 1;
                if(maze[a][j] == 0)
                    queue.offer(new int[]{a, j, d + a - i});
                
                b = j;
                while(b - 1 >= 0 && maze[i][b - 1] != 1)
                    b -= 1;
                if(maze[i][b] == 0)
                    queue.offer(new int[]{i, b, d + j - b});
                
                b = j;
                while(b + 1 < n && maze[i][b + 1] != 1)
                    b += 1;
                if(maze[i][b] == 0)
                    queue.offer(new int[]{i, b, d + b - j});
                
            }
            return -1;
        }
    }
    

Log in to reply
 

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