1. 这道USACO老题为什么十年后还在被反复拿出来做Lake Counting题目编号USACO 2010年10月赛季的Silver组T1是我接触算法竞赛以来见过的最老但最经典的入门题之一。题面讲的是一个农夫在暴风雨后查看自己的农场地里形成了一片片水洼他想知道总共有多少个池塘。输入的是一张由字符构成的矩形地图字符W表示积水.表示干燥土地如果某个W和另一个W在周围八个相邻位置中的任何一个相邻就认为它们属于同一个池塘。最后输出池塘的总数。这道题考察的东西非常纯粹连通块计数。说白了就是给一个二维矩阵找出里面有多少个连成一片的目标区域。算法层面只有两种主流做法——深度优先搜索DFS和广度优先搜索BFS外加一个备选思路——并查集。但奇妙的是就是这个看起来连算法两个字都算不上的题目几乎所有OJ上都有几十甚至上百页的提交记录而且每年都会有新手在它的坑里栽跟头。我当时第一次做这道题是在大一的算法课上用的是C语言写了一个四方向的DFS版本样例过了但交上去WA了好几次。后来仔细读题才发现原题要求的是八方向也就是每个格子周围8个位置都要检查而不是常见的上下左右4个。这种审题不清导致的失误在USACO系列题里特别典型——它不考你多高深的算法而是考你有没有耐心把题读完。如果你正在准备USACO Bronze/Silver组或者刚开始学图论、练DFS这道题是绝对绕不开的入门标杆。它看起来简单但能帮你一次性吃透方向数组的写法、递归/队列的时机选择、边界判断的优先级以及连通块问题的核心套路。这篇文章我会从题目解读、解法选型、代码实现、踩坑记录到变体扩展一步一步讲透把我在反复刷这道题过程中所有值得注意的细节都放进来。2. 连通块计数的解题套路别急着写代码先想清楚遍历这件事2.1 题目本质从找W到找连通块不管用什么解法Lake Counting的核心流程都是一样的从上到下、从左到右遍历整个矩阵。遇到一个未被访问过的W说明发现了一个新池塘答案计数器加一。从这个W出发把所有和它八方向连通的W全部标记为已访问。继续往后扫直到矩阵末尾。关键在于第3步全部标记这一步如果做得不干净后面就会把同一个池塘里的水重复计数。所以这里有一个特别重要的思维转换发现一个池塘的起点之后你要做的是一次彻底的同化——把整个连通块里所有成员都处理掉。这个思路放到图论里就是从某个节点出发遍历所有可达节点只不过这里的图是以矩阵形式隐式存在的节点之间的边就是方向数组定义的相邻关系。理解了这一点你就能明白为什么DFS和BFS是这道题的正解它们本质上都是遍历算法只是展开顺序不同。2.2 为什么主流的题解几乎全是DFS在USACO的官方题解和大部分AC代码里DFS是绝对的主流。原因很现实DFS的代码量最少逻辑最直观只需要一个递归函数加上一个方向数组十几行就能搞定。void dfs(int x, int y) { a[x][y] .; // 直接修改原数组省掉visited数组 for (int k 0; k 8; k) { int nx x dx[k], ny y dy[k]; if (nx 0 nx n ny 0 ny m a[nx][ny] W) { dfs(nx, ny); } } }你注意到一个关键细节了吗就是a[x][y] .这一行。它直接把当前格子的W改成.这样后续遍历到这些格子的时候就不会再重复处理。这种原地标记法省去了额外开一个visited[105][105]布尔数组的开销而且代码更紧凑。对于矩阵规模不超过100×100的题目来说这个做法完全够用。2.3 BFS也能做而且能避免递归栈溢出DFS虽然简洁但有一个隐患如果池塘特别大比如整张地图全是W递归深度会达到N×M的量级。在C里递归层数过深可能导致栈溢出虽然本题的数据范围N, M ≤ 100不足以触发这个问题但如果你在其他OJ上遇到类似的题数据范围变成1000×1000甚至更大DFS就有风险。这时候用BFS就更稳妥。BFS不需要系统栈而是自己维护一个队列把待处理的节点逐个展开。void bfs(int x, int y) { queuepairint, int q; q.push({x, y}); a[x][y] .; while (!q.empty()) { auto [cx, cy] q.front(); q.pop(); for (int k 0; k 8; k) { int nx cx dx[k], ny cy dy[k]; if (nx 0 nx n ny 0 ny m a[nx][ny] W) { a[nx][ny] .; q.push({nx, ny}); } } } }BFS的代码量比DFS多几行但逻辑同样很简单而且由于队列是显式维护的不会有栈溢出问题。对于Lake Counting这道题来说DFS和BFS在性能和代码复杂度上几乎没有区别你习惯哪个用哪个就行。2.4 一个容易忽略的另类思路并查集抛开DFS/BFS这道题其实还有第三种做法并查集Union-Find。思路是把每个W格子看作一个节点检查它右下、下、左下、右这四个方向的W格子如果存在就把它们合并到同一个集合里。最后遍历所有W节点统计有多少个不同的集合这就是池塘数。我为什么说只检查四个方向就够了因为并查集合并是双向的从左上往右下扫描时每个新格子只需要和它已经扫描过的相邻格子合并即可。八方向中位于当前格子左上、上方、右上、左方的格子已经处理过所以只需要检查四个方向就能覆盖所有邻接关系。并查集对这种题来说属于杀鸡用牛刀——代码比DFS长不少而且容易在集合统计上出错——但它是一种很好的思维拓展。如果你正打算学并查集拿这道题练手倒是不错。3. 方向数组和输入处理十个人里有三个人栽在这里3.1 八方向方向数组的三种写法别每次都现推这道题最核心的基础设施就是方向数组。八方向的dx和dy怎么写我见过无数版本这里给你一个最不容易出错的写法int dx[8] {-1, -1, -1, 0, 0, 1, 1, 1}; int dy[8] {-1, 0, 1, -1, 1, -1, 0, 1};这个数组的顺序是从左上角开始按顺时针方向依次列出的8个方向。你可以把它想象成dx和dy的组合方向dxdy左上-1-1上-10右上-11左0-1右01左下1-1下10右下11每次用的时候用for (int k 0; k 8; k)去循环配合nx x dx[k]和ny y dy[k]计算邻居坐标就行。我建议你把这段数组背下来因为后面做迷宫题、扫雷题、岛屿题全都用得上。对了常见的另一种写法是把方向拆成两组int dx[] {-1, -1, -1, 0, 1, 1, 1, 0}; int dy[] {-1, 0, 1, 1, 1, 0, -1, -1};效果一样选一个你顺眼的记住即可。3.2 关键坑四方向还是八方向做题前先拿笔圈出来我在文章开头提到过我最初WA就是因为用了四方向。USACO原题明确说A pond is a set of connected water squares where the connection is considered to be eight-way——八方向。但国内很多OJ把这道题收录时做了改动比如洛谷的P1596就是原题八方向而有些学校OJ上流传的版本却是四方向。更迷惑的是有些数据弱的OJ你用四方向写也能过——因为测试数据里根本没有只有对角相邻的情况。这就是为什么我强烈建议拿到题目后先看样例再找题面里的相邻定义不要凭印象写。如果题面里有eight directions或者周围八格那就是八方向如果只提到上下左右或者四方向那就只用四个方向。2010年USACO原题给了一张图图中两个W斜着相邻也会被算进同一个池塘你可以对着样例手动模拟一遍确认自己的方向数组没问题再开始编码。3.3 字符串读入char数组和string的取舍这道题的输入是N行M列的字符没有空格分隔直接用cin a[i]按行读入是最省事的。注意两点第一如果你用char a[105][105]读入时string不能直接赋给数组要用cin a[i]这样的方式逐行输入。我在网上看到有人用scanf(%s, a[i])也可以但记得a[i]的类型要匹配。第二如果你用vectorstring来存遍历时访问grid[i][j]的写法也很自然。不过要注意string的下标从0开始如果题目给的行列是从1开始编号的比如第1行第1列是W你从0开始遍历时不要被绕晕。3.4 边界判断的两种姿势每次进入下一格之前判断nx和ny是否越界是必须的否则访问a[-1][0]这种非法地址会直接RE。常见写法是if (nx 0 nx n ny 0 ny m a[nx][ny] W)这个条件必须同时满足所以用连接。有些人会写if (nx 0 || nx n || ny 0 || ny m) continue;也就是先排除越界情况再检查a[nx][ny]两种思路都可以。我个人更喜欢后者因为提前把非法情况过滤掉后面的逻辑更清爽if (nx 0 || nx n || ny 0 || ny m) continue; if (a[nx][ny] W) dfs(nx, ny);还有一个细节a[nx][ny] W这个判断要放在越界判断之后因为一旦越界a[nx][ny]本身就是非法访问。这个顺序问题初学者很容易搞反。4. 双解法AC代码与逐行精读照着敲一遍胜过看十遍4.1 DFS完整代码C#include bits/stdc.h using namespace std; int n, m; char a[105][105]; int dx[8] {-1, -1, -1, 0, 0, 1, 1, 1}; int dy[8] {-1, 0, 1, -1, 1, -1, 0, 1}; void dfs(int x, int y) { a[x][y] .; // 把当前格子标记为已访问 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 (a[nx][ny] W) { dfs(nx, ny); } } } int main() { cin n m; for (int i 0; i n; i) { cin a[i]; // 按行读入字符串等价于读入n个字符 } int ans 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (a[i][j] W) { ans; dfs(i, j); } } } cout ans endl; return 0; }这段代码的流程是主函数遍历每个格子遇到W就ans然后从这个格子开始DFS把整个连通块标记掉。DFS里先把自己改成.然后遍历八个邻居只要邻居是W就继续递归。递归结束后这个池塘里的所有W都变成了.外层循环继续找下一个W。有一个经常被问的问题为什么a[x][y] .要放在循环之前如果放在循环后面行不行答案是不行至少效率会差很多。因为如果先进入循环再标记那么相邻的W之间会互相调用A递归BB又递归A造成无限递归。把标记放在最前面才能保证每个格子最多被访问一次。4.2 BFS完整代码C#include bits/stdc.h using namespace std; int n, m; char a[105][105]; int dx[8] {-1, -1, -1, 0, 0, 1, 1, 1}; int dy[8] {-1, 0, 1, -1, 1, -1, 0, 1}; void bfs(int x, int y) { queuepairint, int q; q.push({x, y}); a[x][y] .; // 入队时就要标记防止重复入队 while (!q.empty()) { auto cur q.front(); q.pop(); int cx cur.first, cy cur.second; for (int k 0; k 8; k) { int nx cx dx[k]; int ny cy dy[k]; if (nx 0 || nx n || ny 0 || ny m) continue; if (a[nx][ny] W) { a[nx][ny] .; // 入队前先标记 q.push({nx, ny}); } } } } int main() { cin n m; for (int i 0; i n; i) { cin a[i]; } int ans 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (a[i][j] W) { ans; bfs(i, j); } } } cout ans endl; return 0; }BFS版本的关键点和DFS不同必须在元素入队时立刻标记而不是出队时标记。为什么因为如果不立刻标记同一个格子可能被多个邻居同时判断为未访问导致重复入队队列里出现大量重复元素极端情况下甚至会造成死循环。这算是我刷题时踩过的坑之一现在写BFS一律入队即标记。4.3 代码风格补充关于bits/stdc.h和数组范围上面两个版本都用了#include bits/stdc.h这个万能头文件。在USACO的官方评测环境里这个头文件是可以用的在洛谷、POJ、HDU这些OJ上也没问题。但如果你参加的是某些严格要求标准C的比赛建议还是老老实实写#include iostream、#include queue、#include utility等具体头文件。另外数组开105因为题目说N和M最大是100多开5个是为了防止边界判断时访问到恰好越界的位置——虽然正常逻辑下不会用到但这是C风格数组的惯用防御性写法。5. 我从WA到AC的完整排查过程递归没边界、方向多了、图没读全5.1 第一次提交方向数组下标写错一WA到底我最初自己写的时候方向数组是临时敲的int dx[8] {-1, -1, -1, 0, 0, 1, 1, 1}; int dy[8] {-1, 0, 1, -1, 1, -1, 0, 1};看起来没错对吧但我在循环里写成了for (int k 0; k 4; k)——只循环了前四个方向也就是左上、上、右上、左。结果就是所有只通过对角线相邻的水洼没有被合并答案比预期大。这个错特别隐蔽因为如果测试数据里没有纯对角相邻的情况代码也能AC但只要数据稍微强一点就原形毕露。排查方法很简单构造一个只有对角相邻的样例比如3 3 W.. .W. ...如果代码输出2说明方向处理有问题左上和右下两个W实际应该算一个池塘如果输出1说明方向数组工作正常。做连通块题目先用手算构造一个涉及所有方向的小样例永远是排查方向问题的最快手段。5.2 第二次提交字符串读入导致数组错位一开始我用的是scanf(%s, a[i])来读但是忘了在每行读入前清空缓冲区。可能因为前一行的末尾有\n残留导致第一行数据没读进去矩阵整体错位。这个问题在Windows环境下尤为常见。后来我改成cin a[i]因为cin会自动跳过空白字符读入以空格或换行分隔的字符串不会出错。如果你遇到样例能过但提交RE的情况十有八九是读入问题。我的建议是字符矩阵题目统一用cin 或scanf读字符串别用getchar()一个个读字符——虽然getchar()也能用但你要额外处理\n和\r徒增bug概率。5.3 第三次提交忘记处理多组输入有些OJ的USACO题目会包含多组测试数据或者要求读文件lake.in/lake.out。如果是文件读写一定要在代码开头加freopen(lake.in, r, stdin); freopen(lake.out, w, stdout);USACO官方原题就是文件输入输出。我有一次在USACO官网训练场提交时忘了加这两行结果直接报了File not found。虽然现在大多数国内OJ都用标准输入输出但如果你打算在USACO Training等原版平台刷题文件读写这个习惯必须提前养成。5.4 一次记忆深刻的教训全局变量和局部变量同名有一次我把main函数里也定义了一个局部int n, m结果和全局的n, m冲突导致DFS里读到的n和m是局部变量的垃圾值边界判断完全失效。这个问题C不会报错但运行结果完全错乱。排查了很久才发现是变量遮蔽。命名规范真的很重要全局变量我后来一律加前缀g_比如g_n、g_m从根源上杜绝这类问题。6. 从Lake Counting延伸出去四方向变体、最大面积与进阶思路6.1 四方向变体数池塘(四方向)国内很多OJ上有一个和Lake Counting几乎一样的题名叫数池塘(四方向)或者【基础】数池塘(四方向)区别就是只统计上下左右四个方向上的连通块。这其实是USACO原题的一个简化版本适合刚开始学DFS/BFS的同学。四方向版只需要改方向数组int dx[4] {-1, 0, 1, 0}; int dy[4] {0, 1, 0, -1};核心逻辑一字不改。我建议你把这两个版本都写一遍感受一下方向数组改变对结果的影响。这是一个很好的对照实验能帮你彻底理解连通性定义在连通块问题中的决定性作用。同样的地图四方向和八方向统计出的池塘数可能完全不同。6.2 进阶变体求最大连通块面积Lake Counting只要求统计连通块个数但很多面试题和竞赛题在此基础上加了一问给出最大的连通块面积。做法很简单DFS时返回本次遍历访问了多少个格子int dfs(int x, int y) { a[x][y] .; int cnt 1; for (int k 0; k 8; k) { int nx x dx[k], ny y dy[k]; if (nx 0 || nx n || ny 0 || ny m) continue; if (a[nx][ny] W) { cnt dfs(nx, ny); } } return cnt; }然后在主循环里int area dfs(i, j); maxArea max(maxArea, area);这个问题的变体在LeetCode上就是岛屿的最大面积LeetCode 695只不过那里是四方向、用1表示陆地。你如果掌握了Lake Counting的原题思路几个小时内就能独立AC那道题。6.3 更大数据范围下的解法演进如果N和M变成1000甚至更大DFS可能会栈溢出。这时候有两种选择第一把DFS改成BFS用显式队列代替递归第二如果题目的连通块特别分散还可以用并查集时间复杂度几乎一样是O(N×M)但空间上更灵活。更极端的情况是动态连通性问题——地图本身会变化每过一段时间某个格子从陆地变成水需要实时查询池塘数量。这种题目就不能每次从头DFS得用离线算法、并查集按时间倒序处理或者用线段树维护连通性。当然那是省选级别的难度了不是Lake Counting要考虑的。但对于一个真正想打好基础的人来说知道一条题目的进化链是很有价值的从四方向DFS到八方向DFS到BFS到并查集再到动态连通性每一步都是在前面基础上的自然延伸。7. 我个人实测的一些体会与建议Lake Counting这道题我前前后后做过不下五遍每次都是为了带新人或者复习算法。有一个体会特别深这类入门题其实是最考验基本功的。你可以在10分钟内AC它也可以在一个小时里反复踩坑。两者的区别不在于你知不知道DFS而在于你对边界处理、方向数组、标记时机的敏感度。这里分享几个我平时做题的固定习惯都是从这道题开始养成的一是拿到任何连通块问题先手动模拟一遍样例。不要只盯着样例输出看要真实地在草稿纸上把每个W的邻居都画出来确认自己理解的连通规则和题目一致。二是写DFS时一定把标记放在函数最开头。不管你是在做矩阵DFS还是图DFS只要涉及递归遍历先标记再递归是铁的纪律可以有效防止重复访问和死循环。三是测试的时候专门构造极端数据。比如全W的矩阵、全.的矩阵、只有对角相邻的矩阵、只有一个W的矩阵、边界W的矩阵。这些极端情况能暴露绝大多数bug而且数据构造成本极低。四是学会使用debug输出。在DFS入口打印当前坐标、在递归前打印邻居坐标可以非常直观地看到遍历顺序是否符合预期。如果发现递归方向不对很快就能定位到是方向数组的问题还是边界条件的问题。最后再分享一个和算法无关但很重要的经验USACO的题目命名很规范[USACO10OCT] Lake Counting S中的10OCT代表2010年10月的月赛S代表Silver组。刷USACO的题时注意看题目标号里的组别信息可以判断题目难度Bronze最简单Gold以上就比较难了。Lake Counting作为Silver组的T1难度定位非常清晰——它不是用来难倒你的而是用来确保你掌握搜索这个基础工具的。如果你正处在刚开始学算法、刷题找不到方向的阶段我的建议是不要好高骛远就从这样一道朴素的题开始把它吃透、玩透然后顺着变体去LeetCode上做做岛屿系列再往BFS的最短路问题走。你会发现很多所谓的高阶题底层的解题模型早在Lake Counting里就已经埋下伏笔了。