Minimum Obstacle Removal to Reach Corner LeetCode solution in C++

1
class Solution {
2
 public:
3
  int minimumObstacles(vector<vector<int>> &grid) {
4
    int m = grid.size(), n = grid[0].size();
5
    vector<int> dir = {0, 1, 0, -1, 0};
6
    vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
7
    vector<vector<bool>> vis(m, vector<bool>(n, 0));
8
    deque<pair<int, int>> q;
9
    dist[0][0] = 0;
10
    q.push_front({0, 0});
11
    while (!q.empty()) {
12
      auto cur = q.front();
13
      q.pop_front();
14
      int x = cur.first;
15
      int y = cur.second;
16
      for (int i = 0; i < 4; i++) {
17
        int cx = x + dir[i];
18
        int cy = y + dir[i + 1];
19
        if (cx >= 0 and cy >= 0 and cx < m and cy < n) {
20
          if (!vis[cx][cy]) {
21
            dist[cx][cy] = dist[x][y] + (grid[cx][cy] == 1);
22
            if (grid[cx][cy] == 1)
23
              q.push_back({cx, cy}); // obstacle cell pushed at the end
24
            else
25
              q.push_front({cx, cy}); // empty cell pushed on top
26
            vis[cx][cy] = true;
27
          }
28
        }
29
      }
30
    }
31
    return dist[m - 1][n - 1];
32
  }
33
};