13035.山之谷

markdown
复制
1# 山之谷 题解
2
3## 题目分析
4
5本题给定一个 \(N \times M\) 的网格，每个格子有一个海拔。我们需要统计**山谷**的数量。  
6山谷的定义是：该格子的海拔**不高于**其所有相邻格子（共 8 个方向：上、下、左、右、左上、右上、左下、右下）的海拔。
7
8换句话说，如果一个格子周围（8 连通）没有比它更低的格子，那么它就是一个山谷。需要注意，海拔相等也算作符合条件的山谷。
9
10数据范围：\(1 \le N, M \le 100\)，海拔 \(1 \le h_{i,j} \le 10^5\)。  
11时间限制 1000ms，空间限制 256MB，完全可以用最直接的方法解决。
12
13## 解题思路
14
15最朴素的方法是：遍历每一个格子，检查它的所有 8 个邻居是否都比它大或相等。如果满足条件，就将答案加一。
16
17边界上的格子邻居不足 8 个，需要特殊处理。有两种常见的方法：
18
191. **判断越界**：在检查邻居时，先判断坐标是否在网格范围内，越界则跳过。
202. **添加边界**：给网格外围加一圈“极高”的格子，这样就可以统一使用 8 方向检查，不会因越界而报错，而且逻辑上也等价（边界外的“高山”不会影响山谷的判断）。
21
22由于题目中 \(N,M\) 很小，双重循环的复杂度完全可接受。参考代码采用了添边界的写法，非常简洁。
23
24## 算法说明
25
261. 读入 \(N, M\) 和海拔数组 \(h\)。为了方便，将数组下标设为 \(1 \sim N\) 和 \(1 \sim M\)。
272. 将网格外围一圈（即第 0 行、第 \(N+1\) 行、第 0 列、第 \(M+1\) 列）全部初始化为一个极大值（如 \(10^9\)），代表边界外是“无限高的山”。
283. 使用两重循环遍历所有实际格子 \((i, j)\)（\(1 \le i \le N\)，\(1 \le j \le M\)）。
294. 对于每个格子，用两重循环遍历以它为中心的 \(3 \times 3\) 区域（即 \(i-1 \sim i+1\) 和 \(j-1 \sim j+1\)）。
30   - 如果发现某个邻居的海拔**小于**当前格子的海拔（即 \(h[i][j] > h[i_2][j_2]\)），说明当前格子不是山谷，标记后跳出。
31   - 注意：判断条件不能带等号，因为“不高于”包括相等，只有严格大于时才不是山谷。
325. 如果内层检查完毕，标记仍然为 `true`，则山谷数加一。
336. 输出答案。
34
35## 参考代码及解释
36
37```cpp
38#include <iostream>
39using namespace std;
40
41int main() {
42    int n, m;
43    int h[105][105];          // 多开一些空间用于边界
44    cin >> n >> m;
45
46    // 读入海拔，从 1 开始存储
47    for(int i = 1; i <= n; i++)
48        for(int j = 1; j <= m; j++)
49            cin >> h[i][j];
50
51    // 将外围全部初始化为极大值 (1e9)，代表界外高山
52    for(int i = 0; i <= max(n, m) + 1; i++)
53        h[i][0] = h[0][i] = h[i][m + 1] = h[n + 1][i] = 1e9;
54
55    int ans = 0;
56    // 遍历所有实际格子
57    for(int i = 1; i <= n; i++)
58        for(int j = 1; j <= m; j++) {
59            bool ok = true;
60            // 检查 3×3 区域（包括自身）
61            for(int i2 = i - 1; i2 <= i + 1; i2++)
62                for(int j2 = j - 1; j2 <= j + 1; j2++)
63                    if(h[i][j] > h[i2][j2]) {  // 邻居更低，不是山谷
64                        ok = false;
65                        break;
66                    }
67            ans += ok;   // C++ 中 true 转为 1，false 转为 0
68        }
69    cout << ans;
70    return 0;
71}

代码细节解读

• 数组大小：h[105][105] 足够容纳 (100\times100) 以及额外的一圈边界，定义稍大保证安全。
• 边界初始化：
  for(int i = 0; i <= max(n, m) + 1; i++) 将第 0 行/列和最后一行/列全部设为 (10^9)。这里用了对称赋值，简洁地覆盖了四个边。
• 判断条件：
  if(h[i][j] > h[i2][j2]) —— 注意是严格大于，若大于则说明当前格子比某个邻居高，不满足“不高于所有相邻格子”的定义。
• 包含自身：内循环会检查到自身格子 ((i, j))，但与自身比较时 h[i][j] > h[i][j] 必然为 false，不会影响结果，因此代码无需刻意跳过。
• 答案累加：ans += ok 利用了布尔值到整数的隐式转换，等价于 if(ok) ans++;。

时间复杂度分析

• 网格共有 (N \times M) 个格子。
• 每个格子需要检查最多 (3 \times 3 = 9) 个邻居。
• 总操作次数约为 (9 \times N \times M)。当 (N = M = 100) 时，约为 (9 \times 10^4 = 9 \times 10^4) 次比较，远小于千万级别，在 1s 时限内绰绰有余。
• 空间复杂度：(O(N \times M))，存储海拔数组，同样非常小。

总结

本题考察了对二维网格的遍历以及对“邻居”条件的判断。关键在于处理好边界问题，以及正确理解“不高于”的含义（包含等于）。使用添加边界的方法可以极大简化代码逻辑，避免反复判断坐标是否越界。这是处理网格类问题中非常实用的技巧。