「土」秘法地震

首先考虑到暴力，我们可以枚举四个顶点， 我们可以枚举蓝点，之后根据长方形性质的另外三个点，再遍历正方形即可复杂度为，虽然看起来不错，但仍会TLE。

有没有快速计算一个正方形内有没有1呢。很不错，我们可以使用二维前缀和来优化我们可以记录在他之前有没有一。在查询时我们可以像一维前缀和那样剪掉a[i-1][y]-a[x][j-1]。但是这样仍然会WA，别忘了，记录时要减去a[i-1][j-1]查询时要加上a[i-1][j-1]QAQ。

MY CODE：

#include<bits/stdc++.h>
using namespace std;
char mp[1005][1005];
int a[1005][1005];
int main(){
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++) 
        {
            char x;
            cin>>x;
            a[i][j]=x-'0';
            a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];//记录前缀和
        }
    }
    int ans=0;
    for(int i=1;i<=n-k+1;i++)
    {
        for(int j=1;j<=m-k+1;j++)
        {
            int x=i+k-1;
            int y=j+k-1;
            if(a[x][y]-a[i-1][y]-a[x][j-1]+a[i-1][j-1]>=1) //查询前缀和  
            ans++;
         }
    }
    cout<<ans<<endl;//输出答案啊！！
    return 0;
}