Number of Paths with Max Score LeetCode solution in C++

1
class Solution {
2
 public:
3
  int mod = 1e9 + 7;
4
  map<pair<int, int>, pair<int, int>> h;
5
  pair<int, int> solve(vector<string> &board, int i, int j, int n, int m) {
6
    // base case if you reach top left then 1 path hence return 1
7
    if (i == 0 && j == 0) return {0, 1};
8
    // return 0 as no path is detected
9
    if (i < 0 || j < 0 || i >= n || j >= m || board[i][j] == 'X') return {INT_MIN, 0};
10
    // check if it is stored or not
11
    if (h.find({i, j}) != h.end()) return h[{i, j}];
12
    int no = 0, cnt = 0;
13
    if (board[i][j] != 'S') no = board[i][j] - '0';
14
    // top ,left ,top left
15
    auto a = solve(board, i - 1, j, n, m);
16
    auto b = solve(board, i, j - 1, n, m);
17
    auto c = solve(board, i - 1, j - 1, n, m);
18
    // maxi ans
19
    int curr = (max(a.first, max(b.first, c.first))) % mod;
20
    // if maxi ans == a , b , c then increament count of a ,b,c
21
    if (curr == a.first) cnt += a.second;
22
    if (curr == b.first) cnt += b.second;
23
    if (curr == c.first) cnt += c.second;
24
    return h[{i, j}] = {(curr + no) % mod, cnt % mod};
25
  }
26
  vector<int> pathsWithMaxScore(vector<string> &board) {
27
    auto ans = solve(board, board.size() - 1, board[0].size() - 1, board.size(), board[0].size());
28
    if (ans.first < 0) return {0, 0};
29
    return {ans.first % mod, ans.second % mod};
30
  }
31
};