「土」秘法地震题解

1.题意

有一个 $n\times m$ 的01矩阵。求里面有多少个 $k\times k$ 的矩阵包含1。

2.前置知识

3.正文

这道题写暴力的时间复杂度为 $\mathcal O(n\times m \times k^2)$ ,很明显会超时。
但是如果将 $k^2$ 的检查区间是否符合要求的部分改为二维前缀和就好了，这样时间复杂度就会变成 $\mathcal O (n \times m)$ ,可以AC。

4.代码

#include<stdio.h>
#include<cstring>
using namespace std;
int n, m, k, ans;
int sum[1005][1005];
char s[1005];
int main()
{
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 1; i <= n; i++)
    {
        scanf("%s", s + 1);
        for(int j = 1; j <= m; j++)
            if (s[j] == '1')sum[i][j] = 1;
    }
    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];
    for (int i = 1; i <= n - k + 1; i++)
        for (int j = 1; j <= m - k + 1; j++)
            if (sum[i - 1][j - 1] + sum[i + k - 1][j + k - 1] - sum[i - 1][j + k - 1] - sum[i + k - 1][j - 1] >= 1)ans++;
    printf("%d", ans);
    return 0;
}