Count Square Submatrices with All Ones LeetCode solution in C++

1
class Solution {
2
 public:
3
  int solve(vector<vector<int>> &mat, int n, int m, vector<vector<int>> &dp) {
4
    if (n < 0 or m < 0 or mat[n][m] == 0) return 0;
5

6
    if (dp[n][m] != -1) return dp[n][m];
7

8
    return dp[n][m] = (1 + min({solve(mat, n - 1, m, dp), solve(mat, n - 1, m - 1, dp),
9
                                solve(mat, n, m - 1, dp)}));
10
  }
11

12
  int countSquares(vector<vector<int>> &matrix) {
13
    int n = matrix.size();
14
    int m = matrix[0].size();
15
    int ans = 0;
16

17
    // vector<vector<int>>dp(n , vector<int>(m,-1));
18
    // for(int i = 0 ; i<n ; ++i ){
19
    // for(int j= 0 ; j<m ; ++j ){
20
    // ans += solve( matrix,i , j , dp );
21
    // }
22
    // }
23

24
    vector<vector<int>> dp(n, vector<int>(m, 0));
25

26
    for (int i = 0; i < n; ++i) {
27
      for (int j = 0; j < m; ++j) {
28
        if (i == 0 || j == 0) {
29
          dp[i][j] = matrix[i][j];
30
        } else {
31
          if (matrix[i][j]) dp[i][j] = 1 + min({dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]});
32
        }
33
      }
34
    }
35

36
    for (auto x : dp) {
37
      for (auto y : x) ans += y;
38
    }
39

40
    return ans;
41
  }
42
};