solution

因为地震的区域是固定的。所以枚举一下地震矩形的右下角,然后判断一下这个矩形内是不是含有1就行了。

怎么判断一个矩形内是不是有1?二维前缀和一下,然后计算一下查询矩阵得和是不是比0大就行了。

code

/*
* @Author: wxyww
* @Date:   2020-05-17 15:40:13
* @Last Modified time: 2020-05-17 16:19:51
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 1010;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1; c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0'; c = getchar();
    }
    return x * f;
}
char s[N];
int a[N][N],k,n,m;
int main() {
    n = read(),m = read(),k = read();
    for(int i = 1;i <= n;++i) {
        scanf("%s",s + 1);
        for(int j = 1;j <= m;++j) {
            a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + s[j] - '0';
            // printf("%d ",a[i][j]);
        }
        // puts("");
    }
    int ans = 0;
    for(int i = k;i <= n;++i) {
        for(int j = k;j <= m;++j) {
            int x1 = i - k + 1,y1 = j - k + 1;
            if(a[i][j] - a[i][y1 - 1] - a[x1 - 1][j] + a[x1 - 1][y1 - 1]) ans++;
        }
    }
    cout<<ans;

    return 0;
}