「土」秘法地震

思路：考查二维前缀和，怎么和二维前缀和联系起来？面积为k*k的正方形当存在建筑物（即有1时）会停止施法，而我们要找的是多少种情况会停止施法，换言之就是让我们在n * m的区间找内有多少个k *k的面积内和>0，因此前缀和处理，再扫面一边即可

二维前缀和

在一维的基础上，画图更容易理解,f[i] [j]代表从f[1] [1]到f[i] [j]所围成的矩阵之和，
那么我们第一步就是先构造前缀和，f[i] [j]=f[i-1] [j]+f[i] [j-1]-f[i-1] [j-1]
接下来就是扫描，f[i][j]-f[i-k][j]-f[i][j-k]+f[i-k][j-k]

注意：输入需用字符串读入后换成矩阵，也可用scanf直接读

#include<iostream>
#include<string>
using namespace std;
const int N=1e3+5;
int f[N][N];
string s[N];
int main()
{
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    cin>>s[i];
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    f[i][j]=s[i][j-1]-'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];
     int res=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]!=0)res++;
     }
     cout<<res<<endl;
    return 0;
 }