题目描述
帕秋莉掌握了一种土属性魔法

这种魔法可以在一片k×k大小的一个正方形区域内产生地震

但是如果某片即将产生地震的区域内有建筑物，帕秋莉会停止施法

整个地图大小为n×m，其中一些地方有建筑

请问有多少种可能的情况，使得帕秋莉会停止施法

输入描述:
第一行三个数n, m, k，意义见描述
接下来一个n×m的01矩阵表示这篇区域的情况，1表示这个地方有建筑
输出描述:
输出一个数表示答案

思路：
很简单的题，二维前缀和+枚举即可。

暴力方法就是，枚举每一点为k * k正方形的左上角的顶点，那么只需要计算以该点为边长为k正方形内是不是存在1，存在1那么答案ans++。这样暴力的复杂度是O((n-k+1) * (m-k+1) * k * k)n、m都取1e3，k取500复杂度是500^4 会TLE
容易发现，复杂度主要体现在看每个正方形是不是有1，那么我们可以进行预处理二维前缀和。这样查询每个正方形是不是有1，只需要看正方形内的和是不是大于0，O(1)即可查询

复杂度O(n * m)

#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++){
        cin>>mp[i]+1;
        for(int j=1;j<=m;j++) a[i][j]=mp[i][j]-'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+k-1<=n;i++){
        for(int j=1;j+k-1<=m;j++){
            int x=i+k-1,y=j+k-1;
            if( a[x][y]-a[i-1][y]-a[x][j-1]+a[i-1][j-1])   ans++;

        }
    }
    cout<<ans<<endl;
    return 0;
}