Count Fertile Pyramids in a Land LeetCode solution in C++

1
class Solution {
2
 public:
3
  int f(vector<vector<int>> &grid, int i, int j, vector<vector<int>> &dp) {
4
    if (j < 0 || j >= grid[0].size() || !grid[i][j])
5
      return -1;
6
    else if (dp[i][j] != -1)
7
      return dp[i][j];
8

9
    if (i + 1 >= grid.size() || !grid[i + 1][j]) return dp[i][j] = 0;
10
    return dp[i][j] = 1 + min(f(grid, i + 1, j - 1, dp), f(grid, i + 1, j + 1, dp));
11
  }
12
  int countPyramids(vector<vector<int>> &grid) {
13
    int res = 0, n = grid.size(), m = grid[0].size();
14
    vector<vector<int>> dp(n, vector<int>(m, -1));
15

16
    for (int i = 0; i < n - 1; i++)
17
      for (int j = 0; j < m - 1; j++)
18
        if (grid[i][j]) res += f(grid, i, j, dp);
19

20
    dp = vector<vector<int>>(n, vector<int>(m, -1));
21
    reverse(grid.begin(),
22
            grid.end()); // flip the grid to consider upside-down pyramid
23

24
    for (int i = 0; i < n - 1; i++)
25
      for (int j = 0; j < m - 1; j++)
26
        if (grid[i][j]) res += f(grid, i, j, dp);
27

28
    return res;
29
  }
30
};