1 Map + 1 Queue = Simple BFS (Java)


  • 0

    The idea is similar to Maze I -
    https://discuss.leetcode.com/topic/77600/1-set-1-queue-simple-bfs-java
    The difference is we need to consider distance here, so we can hashmap to record the distance.

    public class Solution {
        public int shortestDistance(int[][] maze, int[] start, int[] destination) {
            PriorityQueue<int[]> pq = new PriorityQueue<>((p1, p2) -> p1[2] - p2[2]); 
            Map<String, Integer> map = new HashMap<>(); 
            pq.offer(new int[]{start[0], start[1], 0}); 
            map.put(start[0] + " " + start[1], 0);
            
            char[] dirs = {'U', 'R', 'D', 'L'}; 
            while (!pq.isEmpty()) {
                int[] cur = pq.poll(); 
                for (char dir: dirs) {
                    int[] next = getStop(maze, cur, dir); 
                    if (!map.containsKey(next[0] + " " + next[1]) || next[2] < map.get(next[0] + " " + next[1])) {
                        map.put(next[0] + " " + next[1], next[2]); 
                        pq.offer(next); 
                    }
                }
            }
            String des = destination[0] + " " + destination[1]; 
            return map.containsKey(des) ? map.get(des) : -1; 
        } 
        
        public int[] getStop(int[][] maze, int[] cur, char dir) {
            int m = maze.length, n = maze[0].length, row = cur[0], col = cur[1], dist = 0; 
            switch (dir) {
                case 'U': while (row != 0 && maze[row - 1][col] != 1) { row--; dist++; } break; 
                case 'R': while (col != n - 1 && maze[row][col + 1] != 1) { col++; dist++; } break; 
                case 'D': while (row != m - 1 && maze[row + 1][col] != 1) { row++; dist++; } break;
                case 'L': while (col != 0 && maze[row][col - 1] != 1) { col--; dist++; } break;
                default: break; 
            }
            
            return new int[]{row, col, dist + cur[2]}; 
        }
    }

Log in to reply
 

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