Dungeon Game LeetCode solution in C++

1
class Solution {
2
 public:
3
  int solve(int i, int j, int m, int n, vector<vector<int>> &grid) {
4
    // if we come out of the grid simply return a large value
5
    if (i >= m || j >= n) return INT_MAX;
6

7
    // calucate health by the 2 possible ways
8
    int down = solve(i + 1, j, m, n, grid);
9
    int right = solve(i, j + 1, m, n, grid);
10

11
    // take the min both both
12
    int health = min(down, right);
13

14
    // we reach the destination when both the sides return INT_MAX
15
    if (health == INT_MAX) {
16
      health = 1; // both are +ve large integers so min health required = 1
17
    }
18

19
    int ans = 0;
20
    if (health - grid[i][j] > 0) {
21
      ans = health - grid[i][j];
22
    } else {
23
      ans = 1;
24
    }
25

26
    return ans;
27
  }
28

29
  int calculateMinimumHP(vector<vector<int>> &dungeon) {
30
    int m = dungeon.size();
31
    int n = dungeon[0].size();
32

33
    return solve(0, 0, m, n, dungeon);
34
  }
35
};