※ 引述《dont (dont)》之铭言：
: 1277. Count Square Submatrices with All Ones
我觉得我的解法超酷
酷一半
后面找的有点丑
要跳过的话也很丑==
##
查区域 不用更新
把mat做成prefix sum
然后slide window
国小数学算面积
class Solution {
public:
int countSquares(vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
int cnt = 0;
// row: prefix sum from left to right
for(int i = 0; i < m; i++){
cnt += mat[i][0];
for(int j = 1; j < n; j++){
cnt += mat[i][j];
mat[i][j] += mat[i][j-1];
}
}
// col prefix sum
for(int j = 0; j < n; j++){
for(int i = 1; i < m; i++){
mat[i][j] += mat[i-1][j];
}
}
int sq = min(m, n);
for(int len = 2; len <= sq; len++){
for(int i = 0; i <= m - len; i++){
for(int j = 0; j <= n - len; j++){
//cout << i << " " << j << " \n";
cnt += check(i, j, len, mat);
}
}
}
return cnt;
}
bool check(int x, int y, int len, vector<vector<int>>& mat){
x

大师