题解 | #「土」秘法地震#

利用二维前缀和，来判断区间是否存在建筑

所以我们就可以利用二维的前缀和来判断，这个区间的和是否大于0，如大于则存在建筑，反之则无。

AC代码如下：

#include <iostream>
#define N 1006
using namespace std;

int n,m,k;
int map[N][N];
int sum[N][N];

int seek(){
    int count = 0;
    for(int i = k; i <= n; i++){
        for(int j = k; j <= m; j++){
            if(sum[i][j] - sum[i][j-k] - sum[i-k][j] + sum[i-k][j-k] > 0)count++;
        }
    }
    return count;
}


int main(){
    string s;
    cin >> n >> m >> k;
    getchar();
    for(int i = 1; i <= n; i++)
    {
        getline(cin,s);
        for(int j = 1; j <= m; j++)
        {
            map[i][j] = s[j-1] - '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] + map[i][j] - sum[i-1][j-1];
        }
    }

    cout << seek() << endl;
    return 0;
}