1091. Shortest Path in Binary Matrix
Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.
A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:
- All the visited cells of the path are 0.
- All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).
The length of a clear path is the number of visited cells of this path.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
int dx[8]{-1,0,1,1,1,0,-1,-1}, dy[8]{-1,-1,-1,0,1,1,1,0}, n(grid.size());
if(grid[n - 1][n - 1] || grid[0][0]) return -1;
queue<pair<int, int>> q;
q.push({0, 0});
grid[0][0] = 1;
while(!q.empty() && !grid[n-1][n-1]) {
auto p = q.front();
q.pop();
for(int i = 0; i < 8; i++) {
int ny(p.first + dy[i]), nx(p.second + dx[i]);
if(0 <= ny && ny < n && 0 <= nx && nx < n && !grid[ny][nx]) {
grid[ny][nx] = grid[p.first][p.second] + 1;
q.push({ny, nx});
}
}
}
return grid[n-1][n-1] ? grid[n-1][n-1] : -1;
}
};
|
