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

题意：

给定一个 $n \times m$ 的二维矩阵，每个位置为 0 或者 1。
询问所有 $k \times k$ 的子矩阵中存在 $1$ 的矩阵个数。

解法：

二维前缀和。

先从一维说起， $n$ 个元素的一维数组为 $a$ ，下标从 $1$ 到 $n$ 。
那么对应的前缀和数组 $s$ 的定义为： $s_i = \sum \limits_{j=1}^ia_i$

求前缀和的递推式为： $\left\{ \begin{aligned} &s_0 = 0 \\ &s_i = s_{i-1} + a_i \space (1 \leq i \leq n) \end{aligned} \right.$

代码实现：

s[0] = 0;
for(int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];

利用前缀和，我们可以 $O(1)$ 求一段区间 $[l, r]$ 的和。

$ans = \sum \limits_{i=l}^ra_i = \sum \limits_{i=1}^{r}a_i - \sum \limits_{i=1}^{l-1}a_i = s_r - s_{l-1}$

再到二维前缀和： $s_{ij} = \sum \limits_{p=1}^i \sum\limits_{q=1}^j a_{pq}$

求二维前缀和的递推式为： $s_{ij} = s_{(i-1)j} +s_{i(j-1)} - s_{(i-1)(j-1)} + a_{ij}$ 。

$O(1)$ 求一个子矩阵 $(x_1, y_1, x_2, y_2)$ 的和为：

$ans = s_{x_2y_2} - s_{(x_1 - 1)y_2} - s_{x_2(y_1 - 1)} + s_{(x_1 - 1)(y_1 - 1)}$ 。

会二维前缀和，那么这道题就结束了。
先求出二维前缀和，然后遍历所有 $k \times k$ 的子矩阵，判断和是否非零，统计答案。

Code：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
int n, m, k, a[N][N], s[N][N];
int main() {
    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]);
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }
    int ans = 0;
    for(int i = k; i <= n; i++)
        for(int j = k; j <= m; j++) {
            int v = s[i][j] - s[i - k][j] - s[i][j - k] + s[i - k][j - k];
            if(v) ans++;
        }
    printf("%d\n", ans);
    return 0;
}