In an N by N square grid, each cell is either empty (0) or blocked (1).
A clear path from top-left to bottom-right has length k if and only if it is composed of cells C_1, C_2, ..., C_k such that:
Adjacent cells C_i and C_{i+1} are connected 8-directionally (ie., they are different and share an edge or corner)
C_1 is at location (0, 0) (ie. has value grid[0][0])
C_k is at location (N-1, N-1) (ie. has value grid[N-1][N-1])
If C_i is located at (r, c), then grid[r][c] is empty (ie. grid[r][c] == 0).
Return the length of the shortest such clear path from top-left to bottom-right. If such a path does not exist, return -1.
Example 1:
Input: [[0,1],[1,0]]
Output: 2
Example 2:
Input: [[0,0,0],[1,1,0],[1,1,0]]
Output: 4
Note:
1 <= grid.length == grid[0].length <= 100
grid[r][c] is 0 or 1
Solution:
class Solution {
int[] dx = new int[]{-1,-1,0,1,1,1,0,-1};
int[] dy = new int[]{0,1,1,1,0,-1,-1,-1};
public int shortestPathBinaryMatrix(int[][] grid) {
if (grid[0][0] != 0) return -1;
int m = grid.length, n = grid[0].length;
if (grid[m - 1][n - 1] != 0) return -1;
Set<Integer> visited = new HashSet();
Deque<Integer> queue = new ArrayDeque();
visited.add(0);
queue.offer(0);
int path = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i ++) {
int curr = queue.poll();
int x = curr / n;
int y = curr % n;
if (x == m - 1 && y == n - 1) {
return path;
}
for (int k = 0; k < 8; k ++) {
int nx = x + dx[k];
int ny = y + dy[k];
int nv = nx * n + ny;
if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 0 && visited.add(nv)) {
queue.offer(nv);
}
}
}
path ++;
}
return -1;
}
}
