【每日一题】「土」秘法地震
「土」秘法地震
https://ac.nowcoder.com/acm/problem/53676
题目
题目描述：帕秋莉掌握了一种土属性魔法
这种魔法可以在一片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/0（方阵怎么办，下面会讲）。
- 这就是这里前缀和的基本思路了。
那么这个前缀和怎么构造呢？
- 其实很简单，知道递推式我们很简单就能得到了：
sum[i][j] = mp[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1]; //某一点的前缀和 = 该点值 + 上面一点的前缀和 + 左边一点的前缀和 - 上边和左边重叠的部分
虽然很好理解，但我还是画了个图：
那这个前缀和该怎么运算呢？怎么弄成方阵呢？
- 我们还是和上面一样，先看图：
- 从图里面我们还是发现，得到某一个方阵的方法是去掉左边和上面的区间，在加上重合的区间。
不过要注意这里是k*k，所以减去的应该是 i - k 和 j - k 的位置的矩形。 - 所以我们判断的公式应该是：
sum[x][y] - sum[x - k][y] - sum[x][y - k] + sum[x - k][y - k]
打代码咯：
- 所以我们先讲原来的矩阵保存下来。
- 然后初始化前缀和（详情看上方小专栏）。
- 随后我们就可以判断方阵递推啦。
- 详情看代码趴~
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;
}
//函数区每日一题 文章被收录于专栏
憨憨的专栏
