题解 | #「土」秘法地震#

题意：在n*m大小的图中有地雷1，在 k * k 的范围内不能有数字为1的地雷 ，如果有情况res++，否则res不变；

题解 ： 本题用二维前缀和思路用区域右下角的点为地雷数量，如果数量大于1则res++;

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int f[N][N];
char str[N];
int n,m,k;

int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {  scanf("%s",str+1);
        for(int j=1;j<=m;j++)
           f[i][j]=str[j]-'0';
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            f[i][j]=f[i][j]+f[i-1][j]+f[i][j-1]-f[i-1][j-1];//前缀和公式
  
    int res=0;
    //从[k][k]开始；
    for(int i=k;i<=n;i++)
         for(int j=k;j<=m;j++)
         {    
             int x;
          x=f[i][j]-f[i-k][j]-f[i][j-k]+f[i-k][j-k];//范围为K，所以i-k,j-k;
             if(x>0) res++;
         }
/*2 1 0 
  1 1 0 
  0 0 1   [k][k]到[n][m]的地雷数情况*/ 
    cout<<res<<endl;
    return 0;    
}