题目描述

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

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

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

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

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

输入描述:

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

输出描述:

输出一个数表示答案

输入

4 4 2

1000

0100

0000

0001

输出

5

备注:

对于30%的数据，n, m≤30

对于100%的数据，n, m≤1000，k≤min(n, m)

思路：

枚举帕迪莉施法的每一块正方形区域，统计有几块区域含有建筑即可。

核心算法：二维前缀和

统计每块区域是否含有建筑时，可以使用二维前缀和预处理一下：

sum[i][j] = Map[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1]j - 1];

其中sum[i][j]记录的是Map[i][j]及其左上角的所有数字之和，取k * k区域内的所有数字之和就好办了

求以sum[i][j]为右下角顶点的k * k正方形内数字之和：

sum[i][j] - sum[i - k][j] - sum[i][j - k] + sum[i - k][j - k]

这样只需要在输入时对sum进行二维前缀和处理，再枚举判断就可以啦

AC代码：

#include <bits/stdc++.h>
using namespace std;
int n, m, k, ans = 0;
char Map[1007][1007];
int sum[1007][1007];
int main(){
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> Map[i][j]; 
            sum[i][j] = Map[i][j] - '0' + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
        }
    }
    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])
                ans++;
        }
    }
    cout << ans;
    return 0;
}

唔这是我的第一篇题解哦

End.