Shortest Path in Binary Matrix
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 lengthk
if and only if it is composed of cellsC_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.
public class Solution {
public int ShortestPathBinaryMatrix(int[][] grid) {
int m = grid.Length;
int n = grid[0].Length;
if(grid[0][0] == 1 || grid[m-1][n-1] == 1){
return -1;
}
bool[][] isVisited = new bool[m][];
for(int i = 0; i < m ; i++){
isVisited[i] = new bool[n];
}
Queue<int[]> q = new Queue<int[]>();
q.Enqueue(new int[]{0, 0});
isVisited[0][0] = true;
int[][] dirs = new int[8][];
dirs[0] = new int[]{-1, 0};
dirs[1] = new int[]{1, 0};
dirs[2] = new int[]{0, -1};
dirs[3] = new int[]{0, 1};
dirs[4] = new int[]{-1,-1};
dirs[5] = new int[]{1,-1};
dirs[6] = new int[]{-1, 1};
dirs[7] = new int[]{1,1};
int ans = 0;
while(q.Count > 0){
int size = q.Count;
for(int l=0 ;l <size;l++) {
var curr = q.Dequeue();
if(curr[0] == m - 1 && curr[1] == n -1){
return ans + 1;
}
for(int i = 0; i < 8; i++){
int x = curr[0] + dirs[i][0];
int y = curr[1] + dirs[i][1];
if(x < 0 || x >= m || y < 0 || y >= m || isVisited[x][y] || grid[x][y] == 1){
continue;
}
q.Enqueue(new int[]{x, y});
isVisited[x][y] = true;
}
}
ans ++;
}
return -1;
}
}
Last updated
Was this helpful?