秘法地震——前缀和

链接：https://ac.nowcoder.com/acm/problem/53676
来源：牛客网

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

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

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

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

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

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

5
备注:
对于30%的数据，n, m≤30
对于100%的数据，n, m≤1000，k≤min(n, m)

首先考虑暴力解法是针对每一个区域，遍历区域内所有元素，看是否有1，这样为O（(m-k) * (n-k) * k²）,明显是很慢的，因此我们用区域内所有的值的和来代替是否有1，只有全为0的时候才不会发生地震，这就是把两个状态用0和1来代替，虽然题目中已经给出0和1的状态，但提示我们以后做题目也可以这样替换。用前缀和可以比较快速的求出各个区域的权值和。

#include<iostream>
#include<algorithm>

using namespace std;

int map[1005][1005];
int main()
{
    int n,m,k,x;
    cin>>n>>m>>k;
    getchar();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            x=getchar()-48;
            map[i][j]=-map[i-1][j-1]+map[i-1][j]+map[i][j-1]+x;
        }
        getchar();
    }
    int cnt=0;
    for(int i=k;i<=n;i++)
    {
        for(int j=k;j<=m;j++)
        {
            if(map[i][j]-map[i-k][j]-map[i][j-k]+map[i-k][j-k])
            {
                cnt++;
            }
        }
    }
    cout<<cnt<<endl;
    getchar();
    getchar();
}