「土」秘法地震

直接二维前缀和,判断区间是不是>0即可.

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+50;
char s[N][N];
int w[N][N];
int f[N][N];
int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>s[i][j];
            if(s[i][j]=='1')    w[i][j]=1;
            else                w[i][j]=0;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+w[i][j];        
        }
    }int ans=0;
    for(int i=k;i<=n;i++)
    {
        for(int j=k;j<=m;j++)
        {
            if(f[i][j]-f[i-k][j]-f[i][j-k]+f[i-k][j-k])    ans++;
        }
    }printf("%d\n",ans);
    return 0;
}