leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1091.cpp (916B)

      1 class Solution {
      2     int n;
      3 
      4     bool valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < n; }
      5 
      6   public:
      7     int shortestPathBinaryMatrix(vector<vector<int>> &grid) {
      8         if (grid[0][0] == 1 || grid.back().back() == 1) return -1;
      9         n = grid.size();
     10 
     11         queue<pair<int, int>> q;
     12         q.push({0, 0});
     13         vector<pair<int, int>> offsets = {{-1, 0}, {-1, 1}, {0, 1},  {1, 1},
     14                                           {1, 0},  {1, -1}, {0, -1}, {-1, -1}};
     15         while (!q.empty()) {
     16             auto [a, b] = q.front();
     17             q.pop();
     18             if (a == n - 1 && b == n - 1) return grid[a][b] + 1;
     19             for (auto [ox, oy] : offsets) {
     20                 int x = a + ox, y = b + oy;
     21                 if (!valid(x, y) || grid[x][y] > 0) continue;
     22                 grid[x][y] = grid[a][b] + 1;
     23                 q.push({x, y});
     24             }
     25         }
     26         return -1;
     27     }
     28 };