统计有多少个单元格,其海拔不高于周围 8 个相邻单元格的海拔。
给定 N 行 M 列的网格,第 i 行 j 列的海拔为 h(i,j)。
如果一个单元格的海拔不高于其所有相邻单元格的海拔,则称该单元格为山谷。相邻包括上、下、左、右、左上、右上、左下、右下共最多 8 个方向。
请统计山谷的数量。
8 邻域方向数组边界处理比较所有邻居
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 N、M;随后 N 行每行 M 个海拔 |
| 输出 | 山谷的数量 |
| 数据范围 | 1 ≤ N, M ≤ 100 |
| 海拔范围 | 1 ≤ h ≤ 10⁵ |
| 判定条件 | 该格 ≤ 所有相邻格(相等也算) |
dx[8]、dy[8],配合循环网格如下,我们逐个格子检查它的 8 个邻居。
7 6 6 7 9 6 5 6 7 6 6 5 7 8 9
| 位置 | 海拔 | 相邻格中的最小值 | 是否 ≤ 最小值 |
|---|---|---|---|
| (1,1) | 7 | 5 | ❌ 7 > 5 |
| (1,2) | 6 | 5 | ❌ |
| (1,3) | 6 | 5 | ❌ |
| (1,4) | 7 | 6 | ❌ |
| (1,5) | 9 | 6 | ❌ |
| (2,1) | 6 | 5 | ❌ |
| (2,2) | 5 | 5 | ✅ 5 ≤ 5 |
| (2,3) | 6 | 5 | ❌ |
| (2,4) | 7 | 6 | ❌ |
| (2,5) | 6 | 7 | ✅ 6 ≤ 7 |
| (3,1) | 6 | 5 | ❌ |
| (3,2) | 5 | 5 | ✅ 5 ≤ 5 |
| (3,3) | 7 | 5 | ❌ |
| (3,4) | 8 | 6 | ❌ |
| (3,5) | 9 | 6 | ❌ |
四个角的格子只有 3 个邻居,边上的格子有 5 个。处理方法是越界就跳过,而不是把网格外当成 0。
| 位置类型 | 邻居个数 | 处理方式 |
|---|---|---|
| 内部格子 | 8 | 全部比较 |
| 边上(非角) | 5 | 越界的 3 个方向跳过 |
| 四个角 | 3 | 越界的 5 个方向跳过 |
// 越界判断:只处理网格内的邻居 int nx = i + dx[d], ny = j + dy[d]; if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
用 dx/dy 两个数组配合循环枚举 8 个邻居
dx[8] = {-1,-1,-1,0,0,1,1,1}、dy[8] = {-1,0,1,-1,1,-1,0,1},两个数组同下标配成一组偏移。写 8 个 if 分别检查上、下、左、右、四个斜角
i-1 >= 0 && j-1 >= 0 这样的边界判断,一共要写 8 次,出错概率明显更高。| 方案 | 代码量 | 漏方向的概率 |
|---|---|---|
| 方向数组 | 约 8 行 | 低 |
| 手写 8 个 if | 约 30 行 | 高 |
第一行输入 N 和 M,随后 N 行每行 M 个数。程序会标出所有山谷。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; int h[105][105]; // 8 个方向的偏移量:上、下、左、右、四个斜角 int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1}; int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1}; int main() { int N, M; scanf("%d %d", &N, &M); for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) scanf("%d", &h[i][j]); int ans = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { bool ok = true; for (int d = 0; d < 8; d++) { int nx = i + dx[d], ny = j + dy[d]; if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue; // 越界跳过 if (h[nx][ny] < h[i][j]) { ok = false; break; } // 有更低的就不是山谷 } if (ok) ans++; } } printf("%d\n", ans); return 0; }
| 代码 | 作用 | 为什么这样写 |
|---|---|---|
dx[8]、dy[8] | 方向偏移 | 同下标配成一组,循环一次得一个邻居 |
if (nx < 0 || nx >= N ...) continue; | 越界判断 | 越界就跳过,绝不能把界外当成 0 |
h[nx][ny] < h[i][j] | 判定条件 | 只要有一个邻居更低,就不是山谷(注意是严格小于) |
if (ok) ans++; | 计数 | 所有邻居都不更低才算山谷 |
写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
3 5 | 3 | 题面样例 |
1 1 | 1 | 单格没有邻居,条件自然成立,算山谷 |
2 2 | 4 | 全部相等,每格都是山谷 |
3 3 | 1 | 只有中心的 1 是山谷 |
1 3 | 1 | 单行时左右两个邻居,3 是山谷 |
邻居 < 自己 才淘汰,即自己 ≤ 所有邻居。需要存整个网格,100 × 100 = 10⁴ 个整数。
✅ 8 万次比较,瞬间完成;这题的关键是方向数组和边界处理。
// 4 邻域与 8 邻域的方向数组 int dx4[4] = {-1, 1, 0, 0}; int dy4[4] = { 0, 0,-1, 1}; int dx8[8] = {-1,-1,-1, 0, 0, 1, 1, 1}; int dy8[8] = {-1, 0, 1,-1, 1,-1, 0, 1}; // 通用邻居遍历模板 for (int d = 0; d < 8; d++) { int nx = i + dx8[d], ny = j + dy8[d]; if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue; // 处理 (nx, ny) } // 用方向数组模拟"走迷宫"时也完全一样
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 方向数组 | 用两个数组表示偏移 | 网格搜索、迷宫、扫雷、BFS/DFS |
| 越界跳过 | 先判断再访问 | 所有二维网格题目的必备写法 |
| "不高于"语义 | 相等也满足 | 所有含"至少/至多/不超过"的判定 |