题目

题目描述：
帕秋莉掌握了一种土属性魔法 
这种魔法可以在一片k×k大小的一个正方形区域内产生地震
但是如果某片即将产生地震的区域内有建筑物，帕秋莉会停止施法
整个地图大小为n×m，其中一些地方有建筑
请问有多少种可能的情况，使得帕秋莉会停止施法

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

输出描述：
输出一个数表示答案

解析

这道题看到的时候，我虎躯一震，这还不简单吗，遍历一遍不就好了！
  • 然后我就写出了这种傻×代码： 
    for (int i = 1; i <= n - 1; i++)
    for (int j = 1; j <= m - 1; j++)
        if (mp[x][y] || mp[x + 1][y] || mp[x][y + 1] || mp[x + 1][y + 1])
            cnt++;
    没错我忘了k是输入的了。

但是这也给了我们暴力灵感：
  • 我们将左上角点代表方阵，然后判断方阵里面有没有1就好了，遍历一圈就好，不过超时是肯定的。

巨巨曾经说过：我们写代码要从会暴力开始提升境界，然后我们来想一下怎么优美的暴力：
  1. 我们上面讲到了，我们可以用一个顶点代替一个方阵。但是我们上面是用了遍历这个方阵，我们何不真用这个点代替方阵呢！
  2. 什么叫真的代替方阵！就是前缀和呀！！！我们这个二维前缀和储存：以原点和该点为对角线的矩形内的数字之和。
  3. 也就是说，我们在判断某一个点时，就能知道他所代表的矩形是否存在1/0（方阵怎么办，下面会讲）。
  4. 这就是这里前缀和的基本思路了。

那么这个前缀和怎么构造呢？
  • 其实很简单，知道递推式我们很简单就能得到了： 
    sum[i][j] = mp[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
//某一点的前缀和 = 该点值 + 上面一点的前缀和 + 左边一点的前缀和 - 上边和左边重叠的部分
    虽然很好理解，但我还是画了个图：

那这个前缀和该怎么运算呢？怎么弄成方阵呢？
  1. 我们还是和上面一样，先看图：
  2. 从图里面我们还是发现，得到某一个方阵的方法是去掉左边和上面的区间，在加上重合的区间。
    不过要注意这里是k*k，所以减去的应该是 i - k 和 j - k 的位置的矩形。
  3. 所以我们判断的公式应该是： 
    sum[x][y] - sum[x - k][y] - sum[x][y - k] + sum[x - k][y - k]

打代码咯：
  1. 所以我们先讲原来的矩阵保存下来。
  2. 然后初始化前缀和（详情看上方小专栏）。
  3. 随后我们就可以判断方阵递推啦。
  4. 详情看代码趴~

AC代码 

#include <iostream>
using namespace std;
//代码预处理区

const int MAX = 1e3 + 7;
int mp[MAX][MAX], sum[MAX][MAX];
//全局变量区

inline bool judge(int x, int y,int k) {
    if (sum[x][y] - sum[x - k][y] - sum[x][y - k] + sum[x - k][y - k]) return true;
    return false;
}
//函数预定义区

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 (judge(i, j, k))
                cnt++;
    printf("%d", cnt);
    return 0;
}
//函数区