每日一题 「土」秘法地震

一道很经典的题目 每次想到是否能不能用前缀和，要考虑前缀和处理出来的数据怎么简化判断，或者能不能判断 既然该题解决的是0和1的有关问题 不难发现如果该正方形不存在1，则其总和为0 ，如此一来，就解决了判断的问题，使用二维前缀数组
按上图
设置M[i][j]记录以（1，1）为左上角端点 以(i,j)为右下角端点的矩形
大矩形=红色矩形+青色矩形-黑色重叠矩形+（i，j）点的数值
不难发现 按M[i][j]=M[i-1][j]+M[i][j-1]-M[i-1][j-1]+a[i][j]前缀即可
接下来直接枚举左上角(i,j)边长为k的正方形
M[i+k-1][j+k-1]-M[i+k-1][j-1]-M[i-1][j+k-1]+M[i-1][j-1]
如果不为0证明存在1
思路很简单，注意边界
坑点：输入由于是输入相邻的01串，直接使用int读入会有问题，它会将01串读成一个数字
枚举是

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e3+7;

char  a[maxn][maxn];///字符读入
int  M[maxn][maxn]={0};

int main()
{
  int  n,m,k;
  scanf("%d%d%d",&n,&m,&k);
  for (int i=1;i<=n;++i)
  {
    for (int j=1;j<=m;++j)
    {
        cin>>a[i][j];
    }
  }
  for (int i=1;i<=n;++i)
  {
    for (int j=1;j<=m;++j)
    {
        M[i][j]=M[i-1][j]+M[i][j-1]-M[i-1][j-1]+(a[i][j]-'0');///处理字符
    }
  }

  ll cnt=0;
  for (int i=1;i<=n-k+1;++i)///注意边界条件 只要n-i+1<=k即可
  {
    for (int j=1;j<=m-k+1;++j)
    {

      if (M[i+k-1][j+k-1]-M[i+k-1][j-1]-M[i-1][j+k-1]+M[i-1][j-1])///是i+k-1并非i+k  
///因为是从M[k]枚举到M[m]   
      {
        ++cnt;
      }
    }
  }
  printf("%lld\n",cnt);


  return 0;
}