leetcode

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

2290.cpp (1040B)

      1 class Solution {
      2   public:
      3     int minimumObstacles(vector<vector<int>> &grid) const {
      4         const int n = size(grid), m = size(grid[0]);
      5 
      6         vector<vector<int>> d(n, vector(m, INT_MAX / 2));
      7         deque<pair<int, int>> dq = {{0, 0}};
      8 
      9         static const int offset[] = {-1, 0, 1, 0, -1};
     10         const auto valid = [&](int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; };
     11 
     12         for (d[0][0] = 0; !dq.empty();) {
     13             const auto [a, b] = dq.front();
     14             dq.pop_front();
     15 
     16             for (int k = 0; k < 4; k++) {
     17                 const int x = a + offset[k + 1];
     18                 const int y = b + offset[k];
     19 
     20                 if (!valid(x, y) || d[x][y] != INT_MAX / 2) continue;
     21                 if (d[a][b] + grid[x][y] >= d[x][y]) continue;
     22 
     23                 d[x][y] = d[a][b] + grid[x][y];
     24 
     25                 if (grid[x][y] == 1)
     26                     dq.emplace_back(x, y);
     27                 else
     28                     dq.emplace_front(x, y);
     29             }
     30         }
     31 
     32         return d[n - 1][m - 1];
     33     }
     34 };