【题解】[土] 秘法地震

这是二维前缀和模板题，先预处理二维前缀和，然后算一下：
对于每个正方形的左上角i,j，下面的式子不等于0就是合法点

然后把答案统计一下输出即可。

二维前缀和知识：
sum表示从1,1开始到i,j这一片平面区域的和。

当画一个图我们可以看出

也就是说平面区域(1,1)~ (i,j)是等于它左边的区域(1,1)~ (i,j-1)加上上面的区域(1,1)~(i-1,j)。此时有重叠的部分(1,1) ~ (i-1,j-1)，再加上当前点(i,j)就可以了。
如下图：

代码：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;

const int maxn=1e3+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;

char mp[maxn][maxn];
int sum[maxn][maxn];

int main(){
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++){
        scanf("%s",mp[i]+1);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
            if(mp[i][j]=='1') sum[i][j]++;
        }
    }
    int ans=0;
    for(int i=1;i<=n-k+1;i++){
        for(int j=1;j<=m-k+1;j++){
            if((sum[i+k-1][j+k-1]-sum[i+k-1][j-1]-sum[i-1][j+k-1]+sum[i-1][j-1])){
                ans++;
            }
        }
    }
    printf("%d",ans);
    return 0;
}