【每日一题】 「土」秘法地震 二维前缀和 + 暴力

题意:

n * m的图上求大小为k*k的正方形中和大于0的个数

思路：

首先要知道暴力怎么枚举 枚举正方形的话由当前位置就可以得到 x = i + k - 1 y = j + k - 1 正好为两个对顶点 然后k*k 算正方形内的值 暴力计算复杂度为
枚举正方形是肯定的 快速得到各个区块内的值 容易想到二维前缀和

#include <bits/stdc++.h>

using namespace std;

#define LL long long
#define ULL unsigned long long
#define mes(x,a) memset(x,a,sizeof(x));
#define sca(a) scanf("%d",&a)
#define lowbit(x)  x & (-x)
#define mk make_pair
#define pb(x) push_back(x)
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define lson v << 1
#define rson v << 1 | 1
#define pii pair<int, int>

inline int read()
{
    int x=0,flag_read=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')
            flag_read=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x*flag_read;
}

const double eps = 1e-9;
const double pi = acos(-1);
const int N = 1005;
const int M = 1e7+5;
const int INF = 0x3f3f3f3f;
const LL mod = 1000000007;

int sum[N][N];
int a[N][N];

int main()
{
    int n , m , k;
    scanf("%d%d%d",&n,&m,&k);

    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            scanf("%1d",&a[i][j]);
        }
    }

    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] - sum[i - 1][j - 1] + (a[i][j] == 1);
        }
    }

    int res = 0;

    for(int i = 1;i + k - 1 <= n;i ++){
        for(int j = 1;j + k - 1 <=m ;j ++){
            int x = i + k - 1;
            int y = j + k - 1;
            if(sum[x][y] - sum[i - 1][y] - sum[x][j - 1] + sum[i - 1][j - 1] > 0){
                res ++ ;
            }

        }
    }

    printf("%d\n",res);

    return 0;
}
/*
4 4
*/