在网格中找 3 × 3 区域,要求内部最高与最低海拔之差 ≤ H,求这些区域中海拔和的最大值。
给定 M 行 N 列的地形图,a(i,j) 表示坐标 (i,j) 的海拔。
停机坪是一个 3 × 3 的区域,要求内部 9 个点的最大高度与最小高度之差不超过 H。求所有适合建造的区域中,内部 9 个点海拔之和的最大值。
滑动窗口二维前缀和最大值与最小值枚举
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 M、N、H;随后 M 行每行 N 个数 |
| 输出 | 合格 3×3 区域中海拔和的最大值 |
| 数据范围 | M, N ≤ 1000 |
| 高度范围 | 1 ≤ H, a ≤ 10⁵ |
| 窗口大小 | 固定 3 × 3 |
M = N = 5,所以有 (5−2) × (5−2) = 9 个候选窗口。
5 5 5 5 5 5 1 5 1 5 5 5 5 5 5 5 2 5 2 5 3 5 5 5 2
| 窗口左上角 | 9 格之和 | 最大值 | 最小值 | 极差 | 极差 ≤ 3? |
|---|---|---|---|---|---|
| (1,1) | 41 | 5 | 1 | 4 | ❌ |
| (1,2) | 37 | 5 | 1 | 4 | ❌ |
| (1,3) | 41 | 5 | 1 | 4 | ❌ |
| (2,1) | 38 | 5 | 1 | 4 | ❌ |
| (2,2) | 31 | 5 | 1 | 4 | ❌ |
| (2,3) | 38 | 5 | 1 | 4 | ❌ |
| (3,1) | 40 | 5 | 2 | 3 | ✅ |
| (3,2) | 39 | 5 | 2 | 3 | ✅ |
| (3,3) | 39 | 5 | 2 | 3 | ✅ |
它们内部都含有海拔 1(第 2 行的 1)
而同一窗口内还有海拔 5
极差 = 5 − 1 = 4 > H = 3 → 不合格
❌ 极差超标
它们只覆盖第 3 ~ 5 行,避开了所有的 1
内部最低是 2(第 4 行的 2)
极差 = 5 − 2 = 3 ≤ 3 → 合格
✅ 三个都合格
左上角 (3,1) 的窗口和 = 40
另两个是 39
最大值为 40
✅ 输出 40
预处理前缀和,窗口和 O(1) 查询;窗口内 9 格枚举求极值
sum = pre[i+3][j+3] - pre[i][j+3] - pre[i+3][j] + pre[i][j],注意右下角是"含"的,所以偏移是 +3 而不是 +2。对每个窗口直接累加 9 个数
| 方案 | 运算量(1000×1000) | 通用性 |
|---|---|---|
| 二维前缀和 | 约 10⁶ + 9 × 10⁶ | 强 |
| 直接累加 | 约 9 × 10⁶ | 弱(窗口变大就退化) |
第一行输入 M、N、H,随后 M 行每行 N 个数。程序会检查所有 3×3 窗口并给出最大和。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; long long a[1005][1005]; long long pre[1005][1005]; // 二维前缀和 int main() { int M, N, H; scanf("%d %d %d", &M, &N, &H); for (int i = 1; i <= M; i++) for (int j = 1; j <= N; j++) { scanf("%lld", &a[i][j]); // 前缀和递推:上 + 左 - 左上 + 自己 pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + a[i][j]; } long long ans = -1; for (int i = 1; i + 2 <= M; i++) { for (int j = 1; j + 2 <= N; j++) { // 求窗口内 9 格的最大值、最小值 long long mx = -1, mn = 1000000; for (int x = 0; x < 3; x++) for (int y = 0; y < 3; y++) { long long v = a[i + x][j + y]; if (v > mx) mx = v; if (v < mn) mn = v; } if (mx - mn <= H) { // 用前缀和 O(1) 求 9 格之和 long long sum = pre[i + 2][j + 2] - pre[i - 1][j + 2] - pre[i + 2][j - 1] + pre[i - 1][j - 1]; if (sum > ans) ans = sum; } } } printf("%lld\n", ans); return 0; }
a[1..M][1..N],这样 pre[i-1] 在 i = 1 时自然是 0,不用额外特判边界。这是网格题里非常常用的技巧。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j] | 前缀和递推 | 容斥原理:减去重复算的左上角 |
i + 2 <= M | 窗口上界 | 窗口占 3 行,所以左上角最多到 M − 2 |
mx - mn <= H | 合格判定 | 注意是极差,不是最大值本身 |
pre[i+2][j+2] - pre[i-1][j+2] - pre[i+2][j-1] + pre[i-1][j-1] | O(1) 求窗口和 | 四个角的前缀和做容斥 |
+ pre[i-1][j-1];② 窗口上界写成 i <= M,数组越界;③ mn 初始化为 0(高度都是正数,会导致极差偏大)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
5 5 3 | 40 | 题面样例 |
3 3 0 | 45 | H = 0 要求完全相等,全 5 的网格恰好满足 |
3 3 100 | 45 | H 足够大,唯一窗口就是答案 |
3 4 1 | 9 | 含 9 的窗口极差为 8 超限,只能选全 1 的窗口 |
需要两个二维数组:原网格和前缀和,各约 10⁶ 个 long long。
✅ 约 1000 万次操作,C++ 瞬间完成,稳过。
// 二维前缀和模板 long long a[1005][1005], pre[1005][1005]; for (int i = 1; i <= M; i++) for (int j = 1; j <= N; j++) { scanf("%lld", &a[i][j]); pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j]; } // 查询以 (r1,c1) 为左上、(r2,c2) 为右下的矩形和 long long rectSum(int r1, int c1, int r2, int c2) { return pre[r2][c2] - pre[r1-1][c2] - pre[r2][c1-1] + pre[r1-1][c1-1]; } // 若窗口固定且很小,也可以用"行前缀 + 列累加"的滑动技巧 // 但要处理窗口内极值,本题直接枚举 9 格最简单
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 二维前缀和 | O(1) 查询任意矩形和 | 矩阵求和、子矩阵统计、图像处理 |
| 固定窗口枚举 | 左上角双层循环 | 卷积、滑窗、局部统计 |
| 极差判定 | max − min ≤ H | 稳定性判断、质量控制 |