题意

现在有一块n*m的区域，帕秋莉对其中一块区域使用魔法，魔***覆盖k*k的区域。如果区域中有建筑，那么停止使用魔法，空地用0表示，建筑用1表示问现在有多少种可能使帕秋莉停止使用魔法。

输入描述

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

输出描述

输出一个数表示答案

解析

是的！！又到了拿出我那张图的时候了

我也没想到居然过了。。。。。。应该是数据太弱了，别学别学

首先我们看下，如果我们要判断这个区域是否能使用魔法，就要确认一下这个区域中是否有建筑，这么来看每一个区域中我们都要遍历KK，这个就是暴力的思路，我们遍历了kK还要遍历整个地图每一个K*K大小的区域，这么这个暴力的时间复杂度达到了很明显能过这一题就是因为数据太弱了，这个时候我们要考虑怎么减少暴力的次数，我们可以试着KK区域的一个点来统计代表这一整个区域的建筑数目，假设我们用左上角这个点，我们在读入的时候就先预处理好，在这个区域中每读入一个数，就加到最左上角，这个是什么，这个就是前缀和，那么怎么实现呢，我们先看下图（这个图来自隔壁博客博客链接） （这里解释一下，这个蓝色的区域是包括了红色的，同样绿**域也是如此）
我们现在要求（i，j）这个位置的前缀和，就是用蓝域加上绿域然后减掉一个红***域，因为重叠了一个，这样我们就可以得到
那么如果我们要判断这个区域中是否有建筑，就是
这样我们就解决了这个问题

代码

#include <iostream>
using namespace std;
typedef long long ll;
const int MAX = 1e3 + 5;
int mp[MAX][MAX], sum[MAX][MAX];
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", &mp[i][j]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            sum[i][j] = mp[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
    int cnt = 0;
    for (int i = k; i <= n; i++)
        for (int j = k; j <= m; j++)
            if (sum[i][j] - sum[i - k][j] - sum[i][j - k] + sum[i - k][j - k])
                cnt++;
    printf("%d", cnt);
    return 0;
}