NC53676 「土」秘法地震（二维前缀和）

题意

帕秋莉掌握了一种土属性魔法

这种魔法可以在一片k×k大小的一个正方形区域内产生地震

但是如果某片即将产生地震的区域内有建筑物，帕秋莉会停止施法

整个地图大小为n×m，其中一些地方有建筑

请问有多少种可能的情况，使得帕秋莉会停止施法

地图用 $01$ 矩阵表示， $1$ 表示有建筑， $0$ 表示没有。

其中， $n,m\leq 1000$ , $k\leq min(n,m)$ 。

分析

枚举正方形的左上顶点 $(i,j)$ ，那么正方形区域为 $[i,i+k-1]*[j,j+k-1]$ 。
现在问题就是判断一个矩形区域中是否有建筑物，这个可以用二维前缀和快速判断。
记 $s_{n,m}=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}a_{i,j}$ 。
根据容斥原理： $s_{n,m}=s_{n-1,m}+s_{n,m-1}-s_{n-1,m-1}+a_{i,j}$ 。
假设要求的区域为 $[a,x]*[b,y]$ 。
那么继续根据容斥原理，整块的和为： $s_{x,y}-s_{a-1,y}-s_{x,b-1}+s_{a-1,b-1}$ 。
最终复杂度是 $O(nm)$

代码如下

#include <bits/stdc++.h>
using namespace std;
int read(){
    int x, f = 1;
    char ch;
    while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
    return x * f;
}
int s[1005][1005];
int main(){
    int i, j, n, m, k, c, x, y, ans = 0;
    n = read(); m = read(); k = read();
    for(i = 1; i <= n; i++){
        for(j = 1; j <= m; j++){
            scanf("%1d", &s[i][j]);
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }
    for(i = 1; i <= n; i++){
        for(j = 1; j <= m; j++){
            if(i + k - 1 > n || j + k - 1 > m) break;
            x = i + k - 1, y = j + k - 1;
            if(s[x][y] - s[i - 1][y] - s[x][j - 1] + s[i - 1][j - 1]) ans++;
        }
    }
    printf("%d", ans);
    return 0;
}