leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1091.cpp (916B)

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 };