NC53676

感受
今天空闲下来，于是做了这道题，乍一看，这不就是拿着一个正方形在地图上跑来跑去吗？
一眼题，巨水

思路
很容易得出，如果一个正方形内有1，那么对答案贡献+1
枚举所有正方形的位置只需要O（n * m），于是考虑如何快速check正方形内有无1。
这不是很眼熟吗？二维区间前缀和，于是就快速秒到这道题目了。
怎么求二维前缀和呢？太简单了，网上博客看一眼就懂了，这里就不赘述了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1000 + 10;
int n, m, k;
char s[maxn][maxn];
int dp[maxn][maxn];///dp[i][j]表示(1, 1) --- (i, j)构成的矩形区域中1的个数
void solve(){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + (s[i][j] == '1');
        }
    }
}
void print(){
    for(int i = 1; i <= n; i++){
        printf("%s\n", s[i] + 1);
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            printf("dp[%d][%d] = %d   ", i, j, dp[i][j]);
        }
        putchar('\n');
    }

}
bool check(int x, int y){
    if(x > n || y > m) return false;
    return true;
}
int get(int x1, int y1, int x2, int y2){
    return dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1];
}
int main(){
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= n; i++){
        scanf("%s", s[i] + 1);
    }
    solve();
    //print();
    int ans = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            int x, y; x = i + k - 1; y = j + k - 1;
            if(!check(x, y)) continue;
            if(get(i, j, x, y)) ans++;
        }
    }
    printf("%d\n", ans);
    return 0;
}