Count Submatrices With All Ones LeetCode solution in C++

1
class Solution {
2
 public:
3
  int numSubmat(vector<vector<int>> &mat) {
4
    int n = mat.size(), m = mat[0].size();
5
    vector<vector<int>> v(n, vector<int>(m + 1, 0));
6
    for (int i = 0; i < n; i++) {
7
      for (int j = 0; j < m; j++) {
8
        v[i][j + 1] = v[i][j] + mat[i][j];
9
      }
10
    }
11
    int res = 0;
12
    for (int i = 0; i < m; i++) {
13
      for (int j = i + 1; j <= m; j++) {
14
        int cnt = 0;
15
        for (int k = 0; k < n; k++) {
16
          int x = v[k][j] - v[k][i];
17
          if (x == (j - i)) {
18
            cnt++;
19
          } else {
20
            res += cnt * (cnt + 1) / 2;
21
            cnt = 0;
22
          }
23
        }
24
        res += cnt * (cnt + 1) / 2;
25
      }
26
    }
27
    return res;
28
  }
29
};