leetcode 1091 - Shortest Path in Binary Matrix

https://leetcode.com/problems/shortest-path-in-binary-matrix/

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
int size = grid.size();
if (grid[0][0] == 1 || grid[size-1][size-1] == 1)
return -1;
vector<vector<bool>> visited(size, vector<bool>(size, false));

queue<pair<int,int>> q;
q.push({0,0});
visited[0][0] = true;
int path = 0;

vector<vector<int>> neighbors = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {-1, -1}, {1, -1}, {-1, 1}};

while (!q.empty()) {
int len = q.size();

path++;

for (int i = 0; i < len; i++) {
auto p = q.front(); q.pop();

if (p.first == size - 1 && p.second == size - 1)
return path;

for (auto n : neighbors) {
int r = p.first + n[0];
int c = p.second + n[1];

if (r < 0 || r >= size || c < 0 || c >= size || grid[r][c] == 1) continue;

if (grid[r][c] == false) {
grid[r][c] = true;
q.push({r, c});
}
}
}
}

return -1;
}
};