1. 题目原文与核心考点1.1 P2919 在说什么这道题来自 USACO 2008 年 11 月月赛 Silver 组在洛谷上的编号是 P2919。题目大意是农夫约翰担心奶牛在农场里乱跑踩坏庄稼就把农场看成一个 N 行 M 列的网格每个格子上写着一个高度。现在要统计这个农场里有多少个“山丘”。山丘的定义有点绕我用自己的话翻译一遍如果若干个格子通过八个方向上下左右加四个斜对角连成一片而且这一片里所有格子的高度都相同同时和这一片区域相邻的外部格子全部都严格低于这一片的高度那这一片区域就是一个山丘。用样例来讲输入是 8 行 7 列的高度矩阵8 7 4 3 2 2 1 0 1 3 3 3 2 1 0 1 2 2 2 2 1 0 0 2 1 1 1 1 0 0 1 1 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1正确输出是 3。我第一次看到这个样例时手算了一遍左上角那片高度为 3 的连通区域外圈接触到的格子全是 2、1、0没有比 3 更高的所以算一个山丘它左下那片高度为 2 的区域虽然面积大但旁边紧挨着高度 3 的格子所以不算独立山丘右侧从第 5 行往下那一列连续的高度 1边界没有更高格子又算一个另外一些孤零零的 1 和 0如果它们的外围恰好没有更高格子也会单独成块。整体思路就是先找“等高连通块”再看它外围一圈的情况。这道题真正考察的重点不是算法本身有多难而是你能不能把“山丘”这个自然语言概念准确翻译成代码里的判定条件。很多选手一开始想当然地认为“最高的格子才算山峰”结果样例直接对不上。1.2 为什么这类题总在信奥里出现USACO 的 Silver 组题目定位是“用基础图论或搜索就能解决”。P2919 属于非常典型的 flood fill 家族。信奥赛场上二维网格上的连通块计数是一个出现率极高的模型统计岛屿数量、统计色块数量、统计连通面积、统计地形盆地或者山峰题目外衣换来换去内核都是“给相邻关系分组”。这类题训练价值高还因为它不是单纯考“你会不会写 BFS/DFS”而是考“你能不能把题意准确翻译成判定条件”。比如本题里那个最容易被忽略的条件——“外部相邻格子必须全部更低才算山丘”如果你读题时没有想明白写出来的代码就会差之毫厘谬以千里。我在带新手刷题时经常说USACO 的题就是阅读理解题样例只是最低级的“体检”真正的坑全藏在文字描述里。1.3 读完题先判断模型看到这种地图类题目我一般要求自己先回答三个问题再动手图是什么节点之间的边怎么定义最终要统计什么图N×M 的网格每个格子是一个节点总节点数 N×M。边本题是八方向相邻也就是八个邻居。统计目标满足“等高连通块 周围全矮”的连通块数量。这三个问题一旦想清楚后面就是套 flood fill 模板。很多同学写搜索题卡住不是因为模板不会背而是因为跳过了建模这一步上来就敲代码结果边界条件、比较对象全都没有着落。先建模再动手永远比边写边想稳。2. 三种关键认知决定你能不能一次做对2.1 “山丘”是一整块等高区域不是单个最高点很多人看到英文 hill 就以为是“最高点”但题目定义完全不是这样。举个例子一个 3×3 的小地图1 2 1 2 2 1 1 1 1中间那个 2 和它右边、下边的 2 连成一片形成高度为 2 的连通块。这个连通块八方向接触到的外部格子全是 1没有更高的格子所以它是一个山丘。如果我把左上角的 1 改成 33 2 1 2 2 1 1 1 1高度为 2 的连通块依然存在但它左上角方向接触到了 3比 2 高所以这个区域就不算山丘了。你看单个格子高度 2 看着还挺突出可边界被更高的 3 压着它就只能算某个大高地的一部分不能独立当选。一句话概括判定规则一个等高连通块能成为山丘取决于它最外圈有没有更高的邻居而不是它内部格子有多高。这个认知是整个算法的地基。我在做这道题之前看了十几篇讨论帖发现大部分错误代码都是在这里理解偏差。2.2 连通性必须看八个方向二维网格的相邻有两种常见定义四方向上下左右和八方向上下左右加四个斜对角。P2919 明确要求按八方向连通。为什么必须是八个方向因为地形上两块高地可能只在一个角上“搭上边”。比如2 1 1 2左上角的 2 和右下角的 2在四方向规则下不相邻但在八方向规则下通过斜对角相连它们属于同一个连通区域。如果题目要求按地形连通划分就不该把它们拆成两座山丘。在本题里漏掉斜方向会导致同一个山丘被拆成两块计数就会变多更麻烦的是边界检查也会跟着错乱因为一个格子可能少看了几个邻居。如果你拿不准题目用四方向还是八方向一定要回到原题描述里看。USACO 的网格题一般会直接写“包括斜角方向”或者给一个示意图。切记不要凭经验蒙。2.3 边界外一层的关系才是判定依据一个等高连通块的“外部邻居”怎么取方法是遍历块内每一个格子检查它的八个邻居如果某个邻居不属于这个块那它就是外部邻居。只要存在一个外部邻居的高度比块内高度高这个块就不是山丘。这里有一个特别容易混淆的细节比较的时候是拿“外部邻居高度”和“整个块的高度”比不是拿“当前格子高度”和“邻居高度”做局部比较。因为同一个连通块里所有格子高度相等所以基准高度是固定的。想通这一点后代码写起来极其简单扩展时遇到等高邻居就继续走遇到更高邻居就标记“不是山丘”遇到更低邻居直接忽略。这样一次遍历就能把“分组”和“判定”两件事同时完成。3. 算法设计从暴力思考到 flood fill3.1 直接从每个格子判断会错在哪最朴素的思路是对每个格子检查八个邻居如果发现周围全部比它低就算一个山峰。这个逻辑乍一看没问题但会漏掉等高连片的情况。反例特别典型2 2 2 2四个格子全是 2它们连成一片。按单个格子判断每个格子的邻居里有等高格子所以“全部低于自己”这个条件不满足于是一个山丘都统计不出来。但按照题目定义四个 2 组成的连通块外围没有更高的格子显然应该算一个山丘。所以必须把等高块当成整体看待不能退化成单点判断。还有一种思路是先对高度排序从高到低处理用并查集合并。这样可以做但把简单问题复杂化了。本题不需要排序flood fill 天然就能承担“分组”功能。记住一个原则网格连通块计数优先考虑 BFS/DFS而不是排序或贪心。3.2 用 flood fill 给等高区域画圈flood fill 的核心动作只有三个选一个未访问的起点沿着连通规则扩展把扩展到的所有点打上标记。应用到本题就是从任意未访问格子 (i,j) 开始。用 BFS/DFS 把所有和它高度相同、且八方向可达的格子全部找出来。扩展过程中时刻检查外部邻居里有没有更高的。如果没有更高的答案加一。重复以上步骤直到所有格子都被访问。为什么 flood fill 能把等高连通块完整圈出来因为两个格子只要高度相同并且紧挨着就会被加入同一个集合而且我使用 visited 数组每个格子只会进入集合一次。最终每个等高连通块有且仅有一次机会作为起点被处理。这个“一格子只属于一块”的性质就是避免重复统计的关键。3.3 怎么避免连通块被重复统计重复统计的根源是同一个连通块里的不同格子都可能成为起点。比如一个高度为 3 的连通块有 10 个格子如果每个格子都各跑一次 flood fill就会统计 10 次。解决办法就是在入队/入栈时立刻标记 visited而不是出队时才标记。用 BFS 时尤其要注意这一点。如果写成“先检查未访问再入队但不立刻标记”同一个格子可能被多个方向重复 push 进队列。不仅浪费时间还会让判定逻辑变得不可控。正确写法是“判断未访问且高度相等 → 立即标记 vis → 入队”。DFS 递归时也是一样进入函数第一行就标记。这算是一个通用经验所有 flood fill 题都建议“先标记再入队”这能省掉一大类重复处理的 bug。4. C 实现全解4.1 递归 DFS 的参考代码先放一版最容易理解、思路和上面分析完全一致的递归 DFS 写法。这段代码适合用来理清逻辑但不一定是最适合直接提交的版本原因我后面会说。#include bits/stdc.h using namespace std; const int MAXN 1005; int n, m; int h[MAXN][MAXN]; bool vis[MAXN][MAXN]; int dx[8] {-1, -1, -1, 0, 0, 1, 1, 1}; int dy[8] {-1, 0, 1, -1, 1, -1, 0, 1}; bool ok; void dfs(int x, int y) { vis[x][y] true; for (int k 0; k 8; k) { int nx x dx[k]; int ny y dy[k]; if (nx 0 || nx n || ny 0 || ny m) continue; if (h[nx][ny] h[x][y]) ok false; if (!vis[nx][ny] h[nx][ny] h[x][y]) { dfs(nx, ny); } } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin n m; for (int i 0; i n; i) { for (int j 0; j m; j) { cin h[i][j]; } } int ans 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (!vis[i][j]) { ok true; dfs(i, j); if (ok) ans; } } } cout ans \n; return 0; }这段代码的可读性很好。每次从 (i,j) 出发时先把 ok 置为 true如果在扩展过程中遇到了比当前块更高的邻居就把 ok 改成 false递归全部结束以后如果 ok 仍为 true说明这个连通块外部没有更高格子ans 加一。注意一个关键细节即使 ok 已经变成 false也必须继续把整个连通块访问完否则后面循环还会从连通块里另一个格子重新开始一次导致统计混乱和答案错误。4.2 从 DFS 改成 BFS为什么更稳递归 DFS 代码虽然直观但有一个很大的隐患递归深度。如果整张地图所有格子高度都一样那么从左上角出发会一口气把所有格子串起来递归深度最多达到 N×M。按照题目上限 1000×1000 来计算就是一百万层。绝大多数评测环境的默认栈空间扛不住表现就是本地小数据全过一提交就 Runtime Error。这种错误最磨人因为它不是逻辑问题而是环境问题。所以我正式提交时更推荐 BFS 写法。BFS 使用 queue 存储待处理坐标不依赖系统调用栈递归多深都无所谓。逻辑上和 DFS 完全一致只是扩展顺序从“一条路走到黑”变成了“层层向外扩散”。在信息学竞赛里能用队列解决的就尽量别用递归这不是胆小而是把风险提前排除掉。4.3 BFS 参考代码逐段拆解下面这个版本是我在 P2919 上实际提交通过的比较稳#include bits/stdc.h using namespace std; const int MAXN 1005; int n, m; int h[MAXN][MAXN]; bool vis[MAXN][MAXN]; int dx[8] {-1, -1, -1, 0, 0, 1, 1, 1}; int dy[8] {-1, 0, 1, -1, 1, -1, 0, 1}; int main() { ios::sync_with_stdio(false); cin.tie(0); cin n m; for (int i 0; i n; i) { for (int j 0; j m; j) { cin h[i][j]; } } int ans 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (vis[i][j]) continue; queuepairint, int q; q.push({i, j}); vis[i][j] true; bool ok true; while (!q.empty()) { int x q.front().first; int y q.front().second; q.pop(); for (int k 0; k 8; k) { int nx x dx[k]; int ny y dy[k]; if (nx 0 || nx n || ny 0 || ny m) continue; if (h[nx][ny] h[i][j]) ok false; if (!vis[nx][ny] h[nx][ny] h[i][j]) { vis[nx][ny] true; q.push({nx, ny}); } } } if (ok) ans; } } cout ans \n; return 0; }逐段拆解一下输入部分没有特别技巧用cin即可但一定要加上ios::sync_with_stdio(false)和cin.tie(0)。这个优化在输入量达到百万级别时是真实有效的我见过太多因为输入太慢而超时的代码。外层双重循环负责枚举起点。每个格子最多作为一个等高连通块的成员被访问一次。每次遇到未访问格子就创建一个空队列把起点入队并立刻标记 visited。ok是这个连通块的“资格证”。只要在扩展过程中看到任何一个外部邻居高度大于h[i][j]就把它设为 false。while 循环里取出队首坐标检查它的八个邻居。越界直接跳过等高且未访问的邻居入队比当前块高的邻居只负责把 ok 置为 false不需要入队比当前块矮的邻居什么都不用做。队列清空后如果 ok 没被置为 false说明这个连通块外圈找不到更高的格子ans。这里我特意用h[i][j]作为基准高度而不是在扩展中写h[x][y]。原因是这个连通块的高度从起点开始就是固定的写h[i][j]能直接表达“我们正在处理的连通块高度”后面代码读起来也更清晰。当然把h[i][j]换成h[x][y]也能过因为块内同高但对于新手来说固定基准更不容易发生逻辑漂移。4.4 方向数组与 visited 的两个高频细节第一个细节方向数组的八个方向必须一一对应。dx 表示行的偏移dy 表示列的偏移我习惯的顺序是dx {-1, -1, -1, 0, 0, 1, 1, 1} dy {-1, 0, 1, -1, 1, -1, 0, 1}按顺序对应左上、上、右上、左、右、左下、下、右下。漏掉一个方向的后果很隐蔽某些斜向相邻的等高块不会被连接山丘数量会变多。要排查方向数组错误可以拿一个 3×3 的小地图把所有格子的八个邻居坐标打印出来肉眼检查一遍这一步花不了两分钟但能省下大量调试时间。第二个细节visited 必须在入队时设置。如果写成“出队时才标记”同一个格子可能被多个邻居重复推进队列。不仅浪费时间还可能在判定边界时产生两次不同的结果直接导致答案不稳定。记住一个口诀先标记再入队永远不要把出队当成标记时机。5. 常见问题与实战排查5.1 样例过但提交错先查这四件事我在给学弟学妹看代码时发现最常见的错误集中在四个地方方向数组只有四个方向。P2919 要求八方向四方向会让等高块被拆开答案偏大。把“比块内高”写成“比当前格子高”。虽然等值块内没区别但这种写法很容易在后续改动中埋雷。找到更高邻居后直接 return 或 break导致连通块没有访问完后面又作为新起点被统计了一次。记住判定可以失败但遍历必须完整。数组开小了。MAXN 至少要比题目上限大一点索引从 0 开始越界判断必须放在访问数组元素之前。先越界 continue再去碰 h[nx][ny]这个顺序任何时候都不能反。如果你把上面四条都检查过大多数问题都能解决。5.2 递归爆栈现象、原因、对策现象非常典型本地跑所有小数据都正确一提交就返回 Runtime Error。尤其当测试数据里存在一个很大的全等高度区域比如整张地图全是同一个数字递归深度直接爆掉。原因就是递归深度达到了 N×M 量级系统栈分配的空间被耗尽。对策有两个一个是从递归 DFS 改成 BFS 队列完全绕开系统栈另一个是自己写栈模拟递归但代码复杂度会明显上升收益不大。所以我建议直接用 BFS 版本。实测 NM1000、全图高度相同时BFS 大约要处理 100 万个节点每个节点做八次邻居判断总操作约 800 万次现代评测机一秒钟内稳稳跑完而递归 DFS 在同样数据下几乎必定爆栈。5.3 自我检查清单准备提交之前我会对着下面这份清单快速扫一遍。这份清单不只对 P2919 有用很多 flood fill 题都能直接复用二维数组大小有没有开够八个方向有没有漏越界判断是否在访问数组元素之前visited 是否在入队时标记是否用一个布尔变量统一管理“外圈有更高”的状态是否在判定失败后仍继续遍历完整连通块输出是否有换行。我通常在正式提交前会先构造几个自定义小样例比如全平地、中间高地被更高处压住、斜对角等高相连这些场景能快速检验方向数组和边界判定是否正确。6. 复杂度、测试与延伸6.1 复杂度和内存占用分析BFS 方案里每个格子最多入队一次每次出队后检查八个邻居所以时间上界是 O(8×N×M)忽略常数就是 O(N×M)。空间方面高度数组和 visited 数组都是 O(N×M)队列在最坏情况下需要保存一张图里的所有格子所以也是 O(N×M)。对 1000×1000 的输入这个复杂度没有任何压力。有些同学会问为什么不用排序如果先按高度从高到低排序然后再处理也能得到答案但会引入 O(N×M log(N×M)) 的排序复杂度完全没必要。flood fill 的 O(N×M) 已经是这个问题能达到的最优复杂度量级了因为每个格子至少要看一遍。6.2 构造几个刁钻测试数据除了题目自带样例我建议你亲手试这几组。第一组整个农场平地2 2 5 5 5 5整个 2×2 全是 5外圈没有更高邻居答案应该是 1。第二组中间一块高地被更高处压住3 3 4 2 3 2 2 1 1 1 1高度 2 的连通块接触到了 4所以它不是山丘两个孤立的 3 各算一个山丘。最终答案要算仔细每次提交前先手算一遍。第三组两个等高块斜角相连2 1 1 2两个 2 在八方向下斜对角相邻属于同一个连通块且周围没有更高格子答案应该是 1。如果用了四方向答案会变成 2这个测试数据能立刻暴露方向数组的问题。6.3 同样的套路还能用在哪些题P2919 的套路可以平移到相当多题目统计二维网格里连通块数量的通用模板统计湖泊数量、岛屿数量改一下连通条件就行统计“盆地”时把比较符号反过来从“外部全矮”变成“外部全高”有些题要求输出最大连通块面积在 BFS 里累计队列处理过的节点数即可结合“高度排序 并查集”还可以处理水位上涨后岛屿数量变化的进阶问题。所以认真把这道题吃透收获的绝不仅仅是一次 AC而是 flood fill 这一类题目的底层认知。我自己第一次写这题时用的就是递归 DFS。样例一遍过自信心爆棚结果提交后返回 Runtime Error。排查了半天才发现测试数据里有一个极大的全等高度区域递归深度直接把栈干爆了。后来我把核心改写成 BFS瞬间清净。从那以后只要是二维网格 flood fill我默认第一版就写 BFS不是递归不能用而是比赛环境里没必要赌系统栈。另一个教训是方向数组不要凭感觉写老老实实一个一个列出来最好本地打印一遍确认。这题难度不算高但它把 flood fill 的坑集中放在了一个场景里——边界、方向、去重、栈空间。你把这几点都踩平之后再去看其他搜索题会发现顺畅很多。