【土】秘法地图

//核心算法二维前缀和，其实在做这道题的同时可以去看一下激光炸弹，两者都是用的二维前缀和；
// 二维前缀和的解释我就不过多赘述了；
#include<iostream>
using namespace std;
#define N 10006
int a[N][N],sum[N][N];
int main(){
int m,n,k;
char op;
cin>>m>>n>>k;
getchar();
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
cin>>op;
a[i][j]=op-'0';//将字符转换为整数存入矩阵；
}
}
for(int i=0;i<=m;i++){
for(int j=0;j<=n;j++){
sum[i][j]=a[i][j]+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];//二维前缀和处理；
}
}
int cnt=0;
for(int i=1;i<=m-k+1;i++){
for(int j=1;j<=n-k+1;j++){//因为从1开始所以结束要加1；
int temp=sum[i-1][j-1]+sum[i+k-1][j+k-1]-sum[i+k-1][j-1]-sum[i-1][j+k-1];//求区间之内的和
if(temp!=0)cnt++;//只要不为0就代表其中有建筑；
}
}
cout<<cnt<<endl;
return 0;
}</iostream>