「土」秘法地震

题目：

思路：

这题的思路当然就是枚举每个释放魔法的地方啦，然后检查这片区域有没有建筑，有的话就要停止施法，++ans。假设我们要施法的区域是下面这个红区域，检查红区域内有无建筑就好

二维前缀和介绍：

当然如果直接暴力的话复杂度 那绝对爆炸的,这里就要引入二维前缀和了，sum[ i ][ j ]表示（0，0）到（i，j）的前缀和。
先给出递推公式 sum[ i ][ j ] = map[ i ][ j ]+sum[ i-1 ][ j ]+sum[ i ][ j-1 ]-sum[ i-1 ][ j-1 ]

看图就知道了，sum[i][j] 表示的是蓝区域红区域加黄区域再加右下角那个

sum[i-1][j] 表示的是蓝区域加黄区域，sum[i][j-1] 表示的是蓝区域加红区域
因为蓝区域重复加了所以要减掉他。
然后我们就预处理完了sum数组，接下来就是要求出（i，j）到（i+k，j+k）区域内有无建筑

要计算红区域内的建筑数

• sum[ x2 ][ y2 ] 表示红区域+紫区域+黄区域+蓝区域
• sum[ x1 ][ y2 ] 表示 黄区域 +紫区域
• sum[ x2 ][ y1 ] 表示 蓝区域 + 紫区域
• sum[ x1 ][ y1 ] 表示 紫区域

稍微想想就知道红区域建筑数等于 sum[x2][y2] - sum[x1][y2] - sum[x2][y1] + sum[x1][y1]

因为只要区域内有建筑就会停止施法，所以判断有无建筑就好。
然后枚举左上角的起始点保证不重复，接下来上代码吧

代码：

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#pragma GCC optimize(3)
typedef long long ll;
#define INF 0x3f3f3f3f
const int mod = 1e9+7;
const int maxn = 1e5+5;
inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
int sum[1005][1005];
int main(){
    int n = read(),m = read(),k = read();
    string s;
    for(int i = 1 ; i <= n ; ++i){
        cin>>s;
        for(int j = 1 ; j <= m ;++j){
            if(s[j-1]=='1') sum[i][j] = 1;
        }
    }
    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]);
        }
    }
    ll ans = 0;
    for(int i = 1 ; i <= n-k+1 ;++i){
        for(int j = 1 ; j <= m-k+1 ;++j){
            int tmp = sum[i+k-1][j+k-1] - sum[i+k-1][j-1] - sum[i-1][j+k-1] + sum[i-1][j-1];
             if(tmp) ans += 1;
        }
    }
    cout<<ans<<endl;
}