牛客小白月赛19 弱版 C

  https://ac.nowcoder.com/acm/contest/2272/C

题意：：

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

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

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

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

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

思路：：二维前缀和思想 ，记录在任意的 K*K 的区间内是否存在1

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int maxn=1e3+5;
 5
 6 char a[maxn];
 7 int num[maxn][maxn];
 8 int b[maxn][maxn];
 9 int n,m,k;
10 int check(int x,int y)
11 {
12     return num[x+k-1][y+k-1]-num[x-1][y+k-1]-num[x+k-1][y-1]+num[x-1][y-1];
13 }
14
15 int main()
16 {
17     scanf("%d%d%d",&n,&m,&k);
18     for(int i=1;i<=n;i++){
19         scanf("%s",a+1);
20         for(int j=1,p=strlen(a+1);j<=p;j++){
21             b[i][j]=a[j]-'0';
22         }
23     }
24     for(int i=1;i<=n;i++){
25         for(int j=1;j<=m;j++){
26             num[i][j]=b[i][j]+num[i-1][j]+num[i][j-1]-num[i-1][j-1];
27         }
28     }
29     int ans=0;
30     for(int i=1;i+k-1<=n;i++){
31         for(int j=1;j+k-1<=m;j++){
32             if(check(i,j)){ans++;}
33         }
34     }
35     cout<<ans<<endl;
36     return 0;
37 }