※ 引述《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