leetcode

0 class Solution {

1 int n;

2

3 bool valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < n; }

4

5 public:

6 int shortestPathBinaryMatrix(vector<vector<int>> &grid) {

7 if (grid[0][0] == 1 || grid.back().back() == 1) return -1;

8 n = grid.size();

9

10 queue<pair<int, int>> q;

11 q.push({0, 0});

12 vector<pair<int, int>> offsets = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1},

13 {1, 0}, {1, -1}, {0, -1}, {-1, -1}};

14 while (!q.empty()) {

15 auto [a, b] = q.front();

16 q.pop();

17 if (a == n - 1 && b == n - 1) return grid[a][b] + 1;

18 for (auto [ox, oy] : offsets) {

19 int x = a + ox, y = b + oy;

20 if (!valid(x, y) || grid[x][y] > 0) continue;

21 grid[x][y] = grid[a][b] + 1;

22 q.push({x, y});

23 }

24 }

25 return -1;

26 }

27 };