企业官网建设流程全解析

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 改成 3：

3 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 fill

3.1 直接从每个格子判断会错在哪

最朴素的思路是：对每个格子检查八个邻居，如果发现周围全部比它低，就算一个山峰。这个逻辑乍一看没问题，但会漏掉等高连片的情况。反例特别典型：

2 2 2 2

四个格子全是 2，它们连成一片。按单个格子判断，每个格子的邻居里有等高格子，所以“全部低于自己”这个条件不满足，于是一个山丘都统计不出来。但按照题目定义，四个 2 组成的连通块外围没有更高的格子，显然应该算一个山丘。所以必须把等高块当成整体看待，不能退化成单点判断。

还有一种思路是先对高度排序，从高到低处理，用并查集合并。这样可以做，但把简单问题复杂化了。本题不需要排序，flood fill 天然就能承担“分组”功能。记住一个原则：网格连通块计数，优先考虑 BFS/DFS，而不是排序或贪心。

3.2 用 flood fill 给等高区域画圈

flood fill 的核心动作只有三个：选一个未访问的起点；沿着连通规则扩展；把扩展到的所有点打上标记。应用到本题就是：

1. 从任意未访问格子 (i,j) 开始。
2. 用 BFS/DFS 把所有和它高度相同、且八方向可达的格子全部找出来。
3. 扩展过程中时刻检查外部邻居里有没有更高的。
4. 如果没有更高的，答案加一。
5. 重复以上步骤，直到所有格子都被访问。

为什么 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; queue<pair<int, 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 样例过但提交错，先查这四件事

我在给学弟学妹看代码时，发现最常见的错误集中在四个地方：

1. 方向数组只有四个方向。P2919 要求八方向，四方向会让等高块被拆开，答案偏大。
2. 把“比块内高”写成“比当前格子高”。虽然等值块内没区别，但这种写法很容易在后续改动中埋雷。
3. 找到更高邻居后直接 return 或 break，导致连通块没有访问完，后面又作为新起点被统计了一次。记住：判定可以失败，但遍历必须完整。
4. 数组开小了。MAXN 至少要比题目上限大一点，索引从 0 开始，越界判断必须放在访问数组元素之前。先越界 continue，再去碰 h[nx][ny]，这个顺序任何时候都不能反。

如果你把上面四条都检查过，大多数问题都能解决。

5.2 递归爆栈：现象、原因、对策

现象非常典型：本地跑所有小数据都正确，一提交就返回 Runtime Error。尤其当测试数据里存在一个很大的全等高度区域，比如整张地图全是同一个数字，递归深度直接爆掉。原因就是递归深度达到了 N×M 量级，系统栈分配的空间被耗尽。

对策有两个：一个是从递归 DFS 改成 BFS 队列，完全绕开系统栈；另一个是自己写栈模拟递归，但代码复杂度会明显上升，收益不大。所以我建议直接用 BFS 版本。实测 N=M=1000、全图高度相同时，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 的坑集中放在了一个场景里——边界、方向、去重、栈空间。你把这几点都踩平之后再去看其他搜索题，会发现顺畅很多。