【每日一题】「土」秘法地震

题号 NC53676
名称 「土」秘法地震
来源 牛客小白月赛19

解题思路

题目要求：求出有多少个 区域内里面有建筑物。

f[i][j] 为前 i 行前 j 列区域中建筑物的数目。
f[i][j] = f[i-1][j] + f[i][j-1] - f[i-1][j-1] + a，其中 a 表示地点 (i,j) 建筑物的数目，即 a = 0 或 a = 1。

以地点 (i,j) 为右下角的 区域中，建筑物的数目 cnt 为：
cnt = f[i][j] - f[i-k][j] - f[i][j-k] + f[i-k][j-k]。
如果 cnt > 0，表示这块区域有建筑物，满足题意，累加计入结果 ans 中。

C++代码

#include<iostream>
#include<vector>
using namespace std;

int main(){
    int n, m, k;
    cin >> n >> m >> k;

    vector<vector<int>> f(n+1, vector<int>(m+1, 0));
    string s;
    for(int i=1; i<=n; ++i){
        cin >> s;
        for(int j=1; j<=m; ++j){
            f[i][j] = f[i-1][j] + f[i][j-1] - f[i-1][j-1];
            if(s[j-1] == &#39;1&#39;)
                ++f[i][j];
        }
    }

    int ans = 0;
    for(int i=k; i<=n; ++i){
        for(int j=k; j<=m; ++j){
            int cnt = f[i][j] - f[i-k][j] - f[i][j-k] + f[i-k][j-k];
            if(cnt > 0)
                ++ans;
        }
    }
    cout << ans << endl;
    return 0;
}