✅ 八连通山谷计数：Python 实现与边界细节全解析

我们来分析这道题： --- ### 🌄 题目核心定义 > **山谷**：一个单元格，其海拔 **不高于**（即 ≤）**所有 8 个方向相邻单元格** 的海拔。 ⚠️ 注意： - 是“不高于”，即 `h[i][j] <= 所有邻居`，**不是严格小于**； - 相邻包括 8 个方向（上、下、左、右、四个对角线），即**八连通**； - 边界上的单元格邻居数少于 8 个（比如角落只有 3 个邻居），只需和**存在的邻居**比较； - 如果某个单元格没有邻居（如 1×1 网格），那它自动满足条件（空真，vacuously true），算作山谷。 --- ### ✅ 解题思路 对每个单元格 `(i, j)`，检查其 8 个方向的邻居： - 枚举 `di` ∈ `[-1, 0, 1]`，`dj` ∈ `[-1, 0, 1]`，跳过 `(0, 0)`； - 计算 `ni = i + di`, `nj = j + dj`； - 若 `(ni, nj)` 在 `[0, N) × [0, M)` 范围内，则是合法邻居； - 检查是否 `h[i][j] <= h[ni][nj]` 对**所有合法邻居**都成立； - 若成立 → 是山谷，计数 `+1`。 --- ### 💡 示例验证（样例输入） ``` 3 5 7 6 6 7 9 6 5 6 7 6 6 5 7 8 9 ``` 我们把矩阵标上行列索引（0-indexed）： ``` (0,0)=7 (0,1)=6 (0,2)=6 (0,3)=7 (0,4)=9 (1,0)=6 (1,1)=5 (1,2)=6 (1,3)=7 (1,4)=6 (2,0)=6 (2,1)=5 (2,2)=7 (2,3)=8 (2,4)=9 ``` 逐个检查（只看可能候选）： - `(0,0)=7`：邻居有 `(0,1)=6`, `(1,0)=6`, `(1,1)=5` → 7 ≤ 6? ❌ → 不是山谷 - `(0,1)=6`：邻居包括 `(0,0)=7`, `(0,2)=6`, `(1,0)=6`, `(1,1)=5`, `(1,2)=6` → 6 ≤ 5? ❌ - `(1,1)=5`：邻居有 8 个（全在范围内）： `7,6,6,5,6,7,6,5` → 最小邻居是 5 → 5 ≤ 所有？✅ 是（5≤5, 5≤6, etc.）→ ✅ 山谷 - `(1,4)=6`：邻居有 `(0,3)=7`, `(0,4)=9`, `(1,3)=7`, `(2,3)=8`, `(2,4)=9` → 6 ≤ all? ✅ → ✅ 山谷 - `(2,1)=5`：邻居：`(1,0)=6`, `(1,1)=5`, `(1,2)=6`, `(2,0)=6`, `(2,2)=7` → 5 ≤ all? ✅（5≤5, 5≤6...）→ ✅ 山谷 共 3 个 → 匹配样例输出。 --- ### ✅ Python 实现（清晰版） ```python def main(): import sys data = sys.stdin.read().split() if not data: return n = int(data[0]) m = int(data[1]) h = [] idx = 2 for i in range(n): row = list(map(int, data[idx:idx+m])) h.append(row) idx += m # 8 directions: dx, dy dirs = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)] valleys = 0 for i in range(n): for j in range(m): is_valley = True for di, dj in dirs: ni, nj = i + di, j + dj if 0 <= ni < n and 0 <= nj < m: if h[i][j] > h[ni][nj]: # 只要有一个邻居更小，就不是山谷 is_valley = False break if is_valley: valleys += 1 print(valleys) if __name__ == '__main__': main() ``` --- ### ⚙️ 复杂度分析 - 时间：O(N × M × 8) = O(NM)，非常高效（最大 100×100×8 = 80,000 次比较） - 空间：O(NM) 存储海拔图 --- ### 🧩 小贴士 & 常见错误 | 错误类型 | 说明 | 如何避免 | |----------|------|-----------| | ❌ 比较时用了 `<` 而非 `<=` | 题目是“不高于”，即允许相等 | 用 `h[i][j] > h[ni][nj]` 判断失败，而非 `>=` | | ❌ 忘记跳过自身 `(0,0)` 方向 | 导致自己和自己比，永远成立 | 显式枚举 8 个方向，不含 `(0,0)` | | ❌ 边界检查写错（如 `ni <= n`） | 数组越界或漏判 | 用 `0 <= ni < n` 安全 | | ❌ 把“山谷”误解为局部最小值（必须 ≤ 所有邻居，不是仅上下左右） | 题目明确说 8 方向 | 一定遍历全部 8 个偏移 | --- ######[AI写代码神器 | 1450点数解答 | 2026-03-16 12:21:41]