Minimum Cost to Make at Least One Valid Path in a Grid LeetCode solution in C++

1
#define vv vector<int>
2

3
class Solution {
4
 public:
5
  int dx[4] = {0, 0, 1, -1};
6
  int dy[4] = {1, -1, 0, 0};
7

8
  int minCost(vector<vector<int>> &grid) {
9
    int m = grid.size();
10
    int n = grid[0].size();
11

12
    priority_queue<vv, vector<vv>, greater<vv>> pq;
13

14
    vector<vector<int>> dp(m + 3, vector<int>(n + 3, INT_MAX));
15

16
    dp[0][0] = 0;
17
    pq.push({0, 0, 0});
18

19
    // there is no need of visited
20

21
    // distance or u can say cost relaxation
22

23
    while (!pq.empty()) {
24
      auto v = pq.top();
25
      pq.pop();
26

27
      int cost = v[0];
28
      int i = v[1];
29
      int j = v[2];
30

31
      if (i == m - 1 && j == n - 1) {
32
        return cost;
33
      }
34

35
      for (int k = 0; k < 4; k++) {
36
        int newi = i + dx[k];
37
        int newj = j + dy[k];
38

39
        if (newi >= 0 && newj >= 0 && newi < m && newj < n) {
40
          if ((k + 1) == grid[i][j]) {
41
            if (dp[newi][newj] > cost) {
42
              dp[newi][newj] = cost;
43
              pq.push({cost, newi, newj});
44
            }
45
          } else {
46
            if (dp[newi][newj] > cost + 1) {
47
              dp[newi][newj] = cost + 1;
48
              pq.push({cost + 1, newi, newj});
49
            }
50
          }
51
        }
52
      }
53
    }
54

55
    if (dp[m - 1][n - 1] != INT_MAX) {
56
      return dp[m - 1][n - 1];
57
    }
58

59
    return -1;
60
  }
61
};