「土」秘法地震

链接：https://ac.nowcoder.com/acm/contest/20960/1025
来源：牛客网

题目描述

帕秋莉掌握了一种土属性魔法

这种魔法可以在一片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)

直接使用二维前缀和，若区域里面的数和大于0，则停止施法。然后记录总数即可。

#include <bits/stdc++.h>

typedef long long ll;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;

const int MAXN = 1004;
int a[MAXN][MAXN];

int main() {
    int n, m, k;
    cin>>n>>m>>k;
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
            scanf("%1d", &a[i][j]);
            a[i][j] += a[i-1][j]+a[i][j-1]-a[i-1][j-1];
        }
    }
    int cnt = 0;
    for (int i=k;i<=n;i++) {
        for (int j=k;j<=m;j++) {
            int sum = a[i][j];
            if (i-k>0) sum-=a[i-k][j];
            if (j-k>0) sum-=a[i][j-k];
            if (i-k>0&&j-k>0) sum+=a[i-k][j-k];
            if (sum>0) cnt++;
        }
    }
    cout<<cnt;
    
    return 0;
}