题解：建造

题目分析

小 A 有一张 $M$ 行 $N$ 列的地形图，每个格子有一个海拔高度。我们需要从图中找到一个 $3 \times 3$ 的正方形区域作为停机坪，要求该区域内 最大值与最小值之差不超过 $H$。在满足条件的所有区域中，求出 9 个格子海拔之和的最大值。

解题思路

由于数据范围 $M, N \le 1000$，整个地形图最多有 $10^6$ 个格子。所有可能的 $3 \times 3$ 区域个数大约为 $(M-2) \times (N-2)$，也在 $10^6$ 级别。

对于每个候选区域，我们只需要检查 $9$ 个格子，统计它们的和、最大值和最小值。总计算量大约为 $9 \times 10^6$，对于 C++ 来说完全可以在一秒之内完成。因此，直接采用暴力枚举即可通过本题。

具体步骤如下：

1. 读入 $M, N, H$ 以及 $M \times N$ 的海拔矩阵 $a$。
2. 初始化答案 max_sum = 0。
3. 枚举 $3 \times 3$ 区域的左上角坐标 $(i, j)$，其中 $1 \le i \le M-2$，$1 \le j \le N-2$。
4. 对于每个区域，遍历其内部的 $3 \times 3 = 9$ 个格子：
   • 累加高度得到 local_sum；
   • 更新 local_max 和 local_min。
5. 如果 local_max - local_min <= H，则用 local_sum 更新全局最大和 max_sum。
6. 枚举结束后，输出 max_sum。

算法复杂度

• 时间复杂度：$O(M \times N \times 9) \approx O(MN)$。当 $M=N=1000$ 时，计算量约为 $9 \times 10^6$，足够高效。
• 空间复杂度：$O(MN)$，用于存储地形图矩阵。

参考代码

cpp
复制
1#include <iostream>
2using namespace std;
3
4int a[1010][1010];  // 存储地形图高度，多开一些空间防止越界
5
6int main() {
7    int M, N, H;
8    cin >> M >> N >> H;
9    
10    // 读入矩阵
11    for (int i = 1; i <= M; ++i) {
12        for (int j = 1; j <= N; ++j) {
13            cin >> a[i][j];
14        }
15    }
16    
17    int max_sum = 0;  // 记录满足条件的最大海拔和
18    
19    // 枚举所有 3×3 区域的左上角 (i, j)
20    for (int i = 1; i <= M - 2; ++i) {
21        for (int j = 1; j <= N - 2; ++j) {
22            // 初始化当前区域的最大、最小、总和
23            int local_max = a[i][j];
24            int local_min = a[i][j];
25            int local_sum = 0;
26            
27            // 遍历 3×3 区域中的每个格子
28            for (int x = 0; x < 3; ++x) {
29                for (int y = 0; y < 3; ++y) {
30                    int height = a[i + x][j + y];
31                    local_sum += height;
32                    if (height > local_max) local_max = height;
33                    if (height < local_min) local_min = height;
34                }
35            }
36            
37            // 判断极差是否不超过 H
38            if (local_max - local_min <= H) {
39                if (local_sum > max_sum) {
40                    max_sum = local_sum;
41                }
42            }
43        }
44    }
45    
46    cout << max_sum;
47    return 0;
48}

代码解释

• 数组大小：题目中 $M,N \le 1000$，我们定义 a[1010][1010] 留有余量，避免边界问题。
• 枚举范围：左上角坐标 $(i, j)$ 的范围是 $1 \le i \le M-2$，$1 \le j \le N-2$，保证右下角不会越界。
• 局部统计：内层两个循环 x 和 y 从 0 到 2，正好遍历 $3 \times 3$ 的格子。
• 更新答案：只有当 local_max - local_min <= H 时才考虑更新 max_sum，保证了答案始终合法。
• 初始值：由于题目保证至少存在一个可行区域，且所有高度均为正数，max_sum 初始化为 0 是安全的。

优化方向（拓展思考）

虽然本题直接暴力即可，但如果数据范围增加到 $M, N \le 3000$ 或更大，我们可以考虑以下优化：

• 使用前缀和 在 $O(1)$ 时间内求出任意矩形区域的和。
• 使用二维滑动窗口 + 单调队列 在 $O(MN)$ 时间内求出所有 $3 \times 3$ 区域的最大值和最小值。

不过对于本题数据规模，上述优化并非必需，暴力枚举已经足够清晰高效。

总结

本题考查了二维数组的基本遍历和极差条件的判断，是一道典型的枚举模拟题。关键点在于正确设定枚举边界，以及对每个候选区域完整统计和与最值。只要细心实现，就能轻松通过。