1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
int n = grid.size();
int dr[] = {-1, -1, 0, 1, 1, 1, 0, -1}, dc[] = {0, 1, 1, 1, 0, -1, -1, -1};
if (grid[0][0] == 1) return -1;
queue<pair<int, int>> q;
q.emplace(0, 0);
grid[0][0] = 1;
int res = 0;
while (!q.empty()) {
++res;
for (int i = q.size(); i > 0; --i) {
auto [r, c] = q.front(); q.pop();
if (r == n - 1 && c == n - 1) return res;
for (int i = 0; i < 8; ++i) {
int rr = r + dr[i], cc = c + dc[i];
if (0 <= rr && rr < n && 0 <= cc && cc < n && grid[rr][cc] == 0) {
q.emplace(rr, cc);
grid[rr][cc] = 1;
}
}
}
}
return -1;
}
};
|