P3282. 探索地块建立

解题思路

本题的暴力解法是找到所有的 c*c 的地块并进行求和运算，这样的时间复杂度为 O(nmc²)，在此不进行赘述。

二维固定滑窗解法

由于地块的大小固定为 c*c，我们要搜索的其实是 grid 中所有大小为 c*c 的窗口中的值的和，这显然可以用 固定滑窗 的思路来完成，基本框架也为 滑窗三问三答。

但本题的难点在于，grid 是一个二维数组，c*c 的地块也是一个二维的滑窗，我们需要在两个方向上进行滑窗过程。

行方向滑窗

首先考虑 行方向（横向，向右） 的滑窗。以示例二为例，只考虑第一行的话，有如下滑窗过程：

上述过程可以由函数 slide_windows_in_row(grid, win_sum, i, m, c, k) 来实现，即：

列方向滑窗

除了行方向的滑窗，还需要考虑 列方向（纵向，向下） 的滑窗。同样以示例二为例，存在以下过程：

而每一个列方向的第一个窗口，都可以通过调用 slide_windows_in_row(grid, win_sum, i, m, c, k) 在行方向滑动。故代码为：

要注意，函数 slide_windows_in_row(grid, win_sum, i, m, c, k) 中的参数 i，为当前搜索地块 最上方那一行的行索引。

二维前缀和解法

本解法和 经典题型、二维区域和检索 - 矩阵不可变 以及 【前缀和】2024E-最大子矩阵和 非常类似。

注意到我们要反复计算大小为 w*w 的子矩阵的和。

由于在 【前缀和】2024E-最大子矩阵和 中用 c 表示子矩阵的左边界，所以在本次讲解中我们换成变量 w 来表示子矩阵的固定边长。

为了避免反复地计算子矩阵和，我们考虑构建大小为 (n+1)*(m+1) 的 二维前缀和矩阵：

对于左上角索引为 (i, j)，大小为 w*w 的子矩阵：

• 上边界：i
• 下边界：i+w-1
• 左边界：j
• 右边界：j+w-1

我们可以用以下公式算出其数字和：

或者更加直接地：

我们再加上关于 i 和 j 遍历的双重循环。由于 i 和 j 的范围分别为从 0 取到 n-w 和 m-w，则整个代码过程如下：

代码

解法一：固定滑窗