GESP 题解库 / 4 级题解 / [GESP202512 四级] 建造 · 第 4 / 25 题
GESP202512 四级 · B4451 · 简单

建造

在网格中找 3 × 3 区域,要求内部最高与最低海拔之差 ≤ H,求这些区域中海拔和的最大值。

📊
M, N ≤ 1000
网格规模
🔢
高度 ≤ 10⁵
数值范围
⚡
O(M × N)
时间复杂度
🎯
二维前缀和 + 枚举
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定 M 行 N 列的地形图,a(i,j) 表示坐标 (i,j) 的海拔。

停机坪是一个 3 × 3 的区域,要求内部 9 个点的最大高度与最小高度之差不超过 H。求所有适合建造的区域中,内部 9 个点海拔之和的最大值。

💡
人话翻译:把每个 3 × 3 的小方块都检查一遍:先看它"最高点减最低点"是否 ≤ H(够平),够平的话再算 9 格之和,最后取最大的和。数据保证至少有一个合格区域,不用考虑无解。

🔍 关键词提取

滑动窗口二维前缀和最大值与最小值枚举

已知条件

项目说明
输入第一行 M、N、H;随后 M 行每行 N 个数
输出合格 3×3 区域中海拔和的最大值
数据范围M, N ≤ 1000
高度范围1 ≤ H, a ≤ 10⁵
窗口大小固定 3 × 3

需要解决的问题

02
思维导图
整理解题思路的全貌
🏗️ 9 格窗口逐个检查
📥 读入
M 行 N 列
高度可能到 10⁵
和可达 9 × 10⁵
用 long long 更稳
📊 二维前缀和
pre[i][j] 表示左上角矩形和
pre[i][j] = 上 + 左 − 左上 + 自己
矩形和 O(1) 查询
窗口和立刻可得
🔍 窗口检查
枚举左上角 (i, j)
求 9 格 max 与 min
max − min ≤ H 才合格
合格就更新答案
⚠️ 易错点
前缀和公式写错
max/min 初始化不当
i、j 的循环上界
H 是"之差"不是"最大值"
03
样例手算推导
样例 5×5 网格逐窗口检查

🧮 样例:5×5 网格,H = 3,答案 40

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)41514❌
(1,2)37514❌
(1,3)41514❌
(2,1)38514❌
(2,2)31514❌
(2,3)38514❌
(3,1)40523✅
(3,2)39523✅
(3,3)39523✅
1
为什么前 6 个窗口都不合格?

它们内部都含有海拔 1(第 2 行的 1)

而同一窗口内还有海拔 5

极差 = 5 − 1 = 4 > H = 3 → 不合格

❌ 极差超标

2
后 3 个窗口为什么合格?

它们只覆盖第 3 ~ 5 行,避开了所有的 1

内部最低是 2(第 4 行的 2)

极差 = 5 − 2 = 3 ≤ 3 → 合格

✅ 三个都合格

3
取最大的和

左上角 (3,1) 的窗口和 = 40

另两个是 39

最大值为 40

✅ 输出 40

🔑
注意"极差"的定义:题目要求的是最大值 − 最小值 ≤ H,不是"最大值 ≤ H",也不是"每个数都 ≤ H"。本样例中所有高度都达到 5 远超 H = 3,但因为窗口内部足够"平",所以依然合格。
04
解法对比
二维前缀和 vs 暴力重算

⚔️ 解法对比

🟢 二维前缀和(推荐) 推荐

预处理前缀和,窗口和 O(1) 查询;窗口内 9 格枚举求极值

  • 时间 O(M × N)
  • 窗口和 O(1)
  • 总共约 9 × 10⁶ 次操作
  • M = N = 1000 也轻松
💡
二维前缀和公式:sum = pre[i+3][j+3] - pre[i][j+3] - pre[i+3][j] + pre[i][j],注意右下角是"含"的,所以偏移是 +3 而不是 +2。

🟠 每个窗口重算 9 格之和

对每个窗口直接累加 9 个数

  • 时间 O(M × N × 9)
  • 约 9 × 10⁶ 次加法
  • 本题其实也够快
  • 但前缀和更显功力
⚠️
实话实说:本题窗口固定 3×3,直接累加 9 格也只有 9 × 10⁶ 次运算,C++ 一秒能跑 10⁸ 次,暴力也能过。但前缀和是可迁移的通用技能,更值得掌握。

📈 性能对比

方案运算量(1000×1000)通用性
二维前缀和约 10⁶ + 9 × 10⁶强
直接累加约 9 × 10⁶弱(窗口变大就退化)
05
算法流程图
预处理前缀和 → 枚举窗口 → 更新答案
开始读入 M、N、H 和网格 a[][]预处理二维前缀和 pre[][]枚举窗口左上角 i 从 0 到 M−3、j 从 0 到 N−3O(1) 求出 9 格之和 sum;枚举 9 格求 max、minmax − min ≤ H 吗?是 ✓ans = max(ans, sum)否 ✗跳过该窗口所有窗口都检查完了吗?输出 ans结束还有窗口 → 继续检查
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🏗️ 停机坪选址计算器

第一行输入 M、N、H,随后 M 行每行 N 个数。程序会检查所有 3×3 窗口并给出最大和。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#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;
}
🔑
前缀和下标从 1 开始最省心:把数组开成 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(高度都是正数,会导致极差偏大)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
5 5 3
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
40题面样例
3 3 0
5 5 5 / 5 5 5 / 5 5 5
45H = 0 要求完全相等,全 5 的网格恰好满足
3 3 100
1 2 3 / 4 5 6 / 7 8 9
45H 足够大,唯一窗口就是答案
3 4 1
1 1 1 9 / 1 1 1 9 / 1 1 1 9
9含 9 的窗口极差为 8 超限,只能选全 1 的窗口
✅
自查清单:① 极差算对了吗?② 前缀和四个角写对了吗?③ 窗口枚举范围对吗?

🚨 易错点清单

⚠️
把"极差 ≤ H"理解成"最大值 ≤ H":题目要求的是窗口内最大值与最小值的差不超过 H。
⚠️
前缀和公式写错:必须是"上 + 左 − 左上 + 自己",漏掉减左上会导致重复计算。
⚠️
窗口上界越界:左上角行下标最大是 M − 3(0 基)或 M − 2(1 基)。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(M × N)
空间复杂度
O(M × N)
M, N 最大
1000
最坏运算
约 10⁷

时间怎么算的?

空间都用在哪?

需要两个二维数组:原网格和前缀和,各约 10⁶ 个 long long。

✅ 约 1000 万次操作,C++ 瞬间完成,稳过。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 二维前缀和模板
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稳定性判断、质量控制
🌟
思考题:如果题目把窗口从 3 × 3 改成 k × k(k 最多 1000),直接枚举 9 格就变成 k² 次,总复杂度 O(M N k²) 会超时。该怎么优化?(提示:用二维滑动窗口 + 单调队列求窗口极值,可以把每行的 k 长区间极值先算出来,再把列方向做一次,整体优化到 O(M × N)。)