# 1 Map + 1 Queue = Simple BFS (Java)

• 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]};
}
}``````

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