Java BFS Implemented with Queue. Much faster than PriorityQueue


  • 0
    L
    public class Solution {
        public int shortestDistance(int[][] maze, int[] start, int[] destination) {
            if (maze == null || maze.length == 0 || maze[0] == null || maze[0].length == 0)
                return 0;
            
            int row = maze.length, col = maze[0].length;
            
            int[][] dist = new int[row][col];
            for (int[] d : dist) {
                Arrays.fill(d, Integer.MAX_VALUE);
            }
            dist[start[0]][start[1]] = 0;
            
            Queue<int[]> queue = new LinkedList<>();
            queue.add(start);
            
            int[][] dir = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
            
            while (!queue.isEmpty()) {
                int[] curr = queue.remove();
                int currDist = dist[curr[0]][curr[1]];
                
                for (int[] d : dir) {
                    int[] tmp = Arrays.copyOf(curr, curr.length);
                    int count = 0;
                    
                    while (valid(maze, tmp, d)) {
                        count++;
                        tmp[0] += d[0];
                        tmp[1] += d[1];
                    }
                    
                    int totalDist = currDist + count;
                    if (totalDist < dist[tmp[0]][tmp[1]] && totalDist < dist[destination[0]][destination[1]]) {
                        dist[tmp[0]][tmp[1]] = totalDist;
                        queue.add(tmp);
                    }
                }
            }
            
            int rst = dist[destination[0]][destination[1]];
            return rst == Integer.MAX_VALUE ? -1 : rst;
        }
        
        private boolean valid(int[][] maze, int[] tmp, int[] d) {
            int x = tmp[0] + d[0], y = tmp[1] + d[1];
            return x >= 0 && x < maze.length && y >= 0 && y < maze[0].length && maze[x][y] == 0;
        }
    }
    

Log in to reply
 

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