class Solution {
int[][] dirs = {{-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,1}, {1, -1}, {1, 0} , {1,1}};
public int shortestPathBinaryMatrix(int[][] grid) {
//bfs
int m = grid.length;
if (m == 1) return grid[0][0] == 0 ? 1 : -1; //1x1 edge case
if (grid[0][0] == 1) return -1; //invalid start
Queue<int[]> q = new ArrayDeque<>();
grid[0][0] = 1; //mark visited
q.offer(new int[] {0,0});
HashMap<Integer,Integer> parent = new HashMap<>();
int level = 1;
while (!q.isEmpty()) {
int size = q.size();
for (int i =0; i < size ;i++) {
int[] cur = q.poll();
for (int[] d : dirs) {
int x = d[0] + cur[0];
int y = d[1] + cur[1];
if (x >= 0 && x < m && y >= 0 && y < m && grid[x][y] == 0) {
parent.put(x*1000+y, cur[0] *1000 + cur[1]);
if (x == m-1 && y == m-1) {
outputPath(x*1000+y, parent);
return level + 1;
}
grid[x][y] = 1;//mark visited
q.offer(new int[] {x,y});
}
}
}
level++;
}
return -1;
}
void outputPath(int key, HashMap<Integer,Integer> map) {
StringBuilder sb = new StringBuilder();
List<String> path = new ArrayList<>();
while (map.containsKey(key)) {
sb.append("[")
.append(key/1000)
.append(",")
.append(key%1000)
.append("]");
path.add(sb.toString());
sb.setLength(0);
key = map.get(key);
}
path.add("[0,0]");
Collections.reverse(path);
System.out.println(String.join("->", path));
}
Comments
0 B
|0 👍
/0 👎
0 B
|👍
/👎