「土」秘法地震
答题卡
http://www.nowcoder.com/questionTerminal/68d4cc423c824d5881ecb314c78f0d1d
「土」秘法地震
思路：考查二维前缀和，怎么和二维前缀和联系起来？面积为k*k的正方形当存在建筑物（即有1时）会停止施法，而我们要找的是多少种情况会停止施法，换言之就是让我们在n * m的区间找内有多少个k *k的面积内和>0，因此前缀和处理，再扫面一边即可
二维前缀和
在一维的基础上，画图更容易理解,f[i] [j]代表从f[1] [1]到f[i] [j]所围成的矩阵之和，
那么我们第一步就是先构造前缀和，f[i] [j]=f[i-1] [j]+f[i] [j-1]-f[i-1] [j-1]
接下来就是扫描，f[i][j]-f[i-k][j]-f[i][j-k]+f[i-k][j-k]
注意：输入需用字符串读入后换成矩阵，也可用scanf直接读
#include<iostream>
#include<string>
using namespace std;
const int N=1e3+5;
int f[N][N];
string s[N];
int main()
{
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
cin>>s[i];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f[i][j]=s[i][j-1]-'0';
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f[i][j]+=f[i-1][j]+f[i][j-1]-f[i-1][j-1];
int res=0;
for(int i=k;i<=n;i++)
{
for(int j=k;j<=m;j++)
if(f[i][j]-f[i-k][j]-f[i][j-k]+f[i-k][j-k]!=0)res++;
}
cout<<res<<endl;
return 0;
} 
小米集团公司福利 868人发布
