「土」秘法地震

题目链接
题意：
$有一个n*m的01矩阵，1代表有石块$
$帕秋莉可以在其中任意一个k*k的正方形区域施法$
$但是如果区域中有石块那么则不能施法$
$问有多少种情况不能施法$
题解：
$其实，问题说的就是这个n*m矩阵中$
$找k*k的正方形，所有的正方形中有几个是包含1的$
$所以可以算这个k*k正方形里数的和是多少$
$如果大于0说明里面有1$
$但是这道题数据范围,n,m<=1e3,k<=min(n,m)$
$我们能用的最高复杂度就是O(nm)$
$所以我们想要算矩阵，需要借助一下二维前缀和计算$
$二维前缀和其实就是从点(1,1)到(n,m)这个矩阵的所有和$
$算法就是先用(n-1,m)+(n,m-1)+a[n][m]$
$把(1,1)到(n-1,m)和(1,1)到(n,m-1)的矩阵画出来$
$我们会发现有这个重叠部分$
$那就是(1,1)到(n-1,m-1)，直接减去这一部分即可$
$这样就直接算出来了二维前缀和$
$然后我们就可以枚举正方形块，看他的k*k矩阵$
$k*k矩阵就是用二维前缀和操作一下$
$我枚举的正方形是正方形右下角的点，所以这个矩阵如下$
$sum[i][j]-sum[i-k][j]-sum[i][j-k]+sum[i-k][j-k]$
$用这个点的二维前缀和，减去左边多出的，和上边多出的$
$会发现两个多出的部分重叠了一个小正方形，加上多减去的即可$
代码如下

/*
    Author:zzugzx
    Lang:C++
    Blog:blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

char g[1010][1010];
int sum[1010][1010];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            cin>>g[i][j];
            if(g[i][j]=='1')sum[i][j]++;
        }
    int ans=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
    for(int i=k;i<=n;i++)
        for(int j=k;j<=m;j++){
            int cnt=sum[i][j]-sum[i-k][j]-sum[i][j-k]+sum[i-k][j-k];
            if(cnt>0)ans++;
        }
    cout<<ans<<endl;
    return 0;
}