1277. Count Square Submatrices with All Ones
Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
int r = 0, res = 0, n = matrix.size(), m = matrix[0].size();
vector<int> c(m, 0);
for(int i = 0; i < n; i++, r = 0) {
for(int j = 0; j < m; j++) {
if(matrix[i][j] == 0) {
c[j] = r = 0;
} else {
r += 1; c[j] += 1; res += 1;
int mi = min(r, c[j]);
for(int k = 1; k < mi; k++) {
if(c[j - k] > k) res++;
mi = min(mi, c[j-k]);
}
}
}
}
return res;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int countSquares(vector<vector<int>> &matrix) {
int n(matrix.size()), m(matrix[0].size()), res(matrix[0][0]);
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
if (!matrix[i][j]) continue;
int diagonal = min(matrix[i - 1][j], matrix[i][j - 1]);
matrix[i][j] = matrix[i - diagonal][j - diagonal] ? diagonal + 1 : diagonal;
res += matrix[i][j];
}
}
for(int i = 1; i < n; i++) res += matrix[i][0];
for(int i = 1; i < m; i++) res += matrix[0][i];
return res;
}
};
|
