Number of Ways of Cutting a Pizza LeetCode solution in C++

1
class Solution {
2
 private:
3
  int mod = 1000000000 + 7;
4
  vector<vector<vector<int>>> mem;
5
  vector<vector<bool>> colContainsApple, rowContainsApple;
6
  int solve(vector<string> &pizza, int r, int c, int cuts) {
7
    int m = pizza.size(), n = pizza[0].size();
8
    if (cuts == 0) {
9
      for (int row = r; row < m; row++) {
10
        if (rowContainsApple[row][c]) {
11
          return 1;
12
        }
13
      }
14
      for (int col = c; col < n; col++) {
15
        if (colContainsApple[r][col]) {
16
          return 1;
17
        }
18
      }
19
      return 0;
20
    } else if (mem[r][c][cuts] != -1) {
21
      return mem[r][c][cuts];
22
    } else {
23
      int ans = 0;
24
      bool present = false;
25
      for (int row = r; row <= m - 2; row++) {
26
        if (!present and rowContainsApple[row][c]) {
27
          present = true;
28
        }
29
        if (present) {
30
          ans = (ans % mod + solve(pizza, row + 1, c, cuts - 1) % mod) % mod;
31
        }
32
      }
33
      present = false;
34
      for (int col = c; col <= n - 2; col++) {
35
        if (!present and colContainsApple[r][col]) {
36
          present = true;
37
        }
38
        if (present) {
39
          ans = (ans % mod + solve(pizza, r, col + 1, cuts - 1) % mod) % mod;
40
        }
41
      }
42
      return mem[r][c][cuts] = ans;
43
    }
44
  }
45

46
 public:
47
  int ways(vector<string> &pizza, int k) {
48
    int m = pizza.size(), n = pizza[0].size();
49
    mem = vector<vector<vector<int>>>(m, vector<vector<int>>(n, vector<int>(k, -1)));
50
    colContainsApple = vector<vector<bool>>(m, vector<bool>(n, false));
51
    rowContainsApple = vector<vector<bool>>(m, vector<bool>(n, false));
52
    for (int col = 0; col < n; col++) {
53
      for (int row = m - 1; row >= 0; row--) {
54
        if (pizza[row][col] == 'A' or (row != m - 1 and colContainsApple[row + 1][col])) {
55
          colContainsApple[row][col] = true;
56
        }
57
      }
58
    }
59
    for (int row = 0; row < m; row++) {
60
      for (int col = n - 1; col >= 0; col--) {
61
        if (pizza[row][col] == 'A' or (col != n - 1 and rowContainsApple[row][col + 1])) {
62
          rowContainsApple[row][col] = true;
63
        }
64
      }
65
    }
66
    return solve(pizza, 0, 0, k - 1);
67
  }
68
};