USACO的白银组历来是个分水岭过了铜牌之后很多人第一次在这里感到“算法题突然变得不那么直给了”。2005年3月这套白银组真题放在今天看难度不算高但它有一道题非常典型几乎是把“连通块计数”这个考点焊死在了入门搜索的必经之路上——就是网络热词里提到的“数池塘四方向”。这道题也叫Lake Counting的一个变体很多新手第一次接触DFS/BFS就是从它开始的。我自己刷这道题的时候还在上大学当时觉得“这不就是数有几个水坑嘛”结果一写就翻车要么死循环要么边界溢出要么方向数组里四个方向写错两个。后来带学生刷USACO发现大家在同一个地方踩的坑几乎一模一样。所以这篇就把2005年3月白银组的这道数池塘题彻底拆开讲从题目理解、解法选型、代码实现到调试排查一次说清楚。适合刚过铜牌、准备冲白银组的人也适合那些想用一道题把DFS连通块彻底搞懂的人。1. 2005年3月白银组这道题到底在考什么1.1 题目长什么样原题描述很直白给你一个 n 行 m 列的网格地图每个格子里只有两种状态一种是水用字符W表示另一种是陆地用.表示。所谓“池塘”就是由若干个相邻的水格子连成的一个区域。注意这里的相邻只算上下左右四个方向也就是四连通斜对角方向上的水格子不算连在一起。题目要求你输出这张地图里总共有多少个池塘。光看文字可能不够直观我构造一个简单的测试数据输入 4 5 .W.W. .W.W. .W.W. ....W 输出 3在这个例子里第一列和第二列各有三行是连续的W它们各自构成一个池塘最右下角那个单独的W虽然离左边那几个水格子很近但斜对角不算连通所以它自己也是一个池塘。最后答案是3。这个题输入方式也很传统第一行两个整数 n 和 m接下来 n 行是地图字符串字符之间没有空格。输出就一个整数池塘数量。1.2 考点拆解连通块计数与洪水填充这道题的本质是把一个二维网格里所有“连在一起的水格子”划分成若干个组然后数组的个数。在算法领域这个操作叫连通块计数实现它的经典手法叫洪水填充Flood Fill你可以想象成往一个水坑里倒墨水墨水会自动沿着连通的格子扩散直到把这个水坑全部染色然后再去下一个水坑。USACO把这道题放在白银组是有道理的。它不会像铜牌题那样直接告诉你“请用搜索”而是把搜索藏在一个日常场景里。你需要自己想到每个W都可能是某个池塘的起点从一个起点出发把所有相邻的W全部访问并标记掉下次再遇到还没标记的W就说明发现了一个新池塘。能想明白这一步银组入门级的搜索题基本上就通了一半。另外这个题目还有一个容易被忽略的点它明确写了“四方向”。USACO里还有一道更经典的八方向版本也就是行差和列差绝对值不超过1都算相邻。四方向版本相对简单但它更干净地突出了“方向数组”这个基础概念。你在做题时最好先确认清楚题目要求是四方向还是八方向这一步搞错后面全白写。2. 解法选型为什么建议新手从DFS入手2.1 DFS与BFS的取舍在地图类的连通块问题上DFS深度优先搜索和BFS广度优先搜索都能做核心思想是一样的找到一个水格子就沿着它一路把所有连通的水格子都找出来并标记。区别只在于扩散的顺序DFS是“一条路走到黑”BFS是“一圈一圈往外扩”。我个人的建议是这道题优先用DFS。原因很实际代码量少理解成本低。一个递归函数加上一个方向数组加起来不到二十行非常适合第一次接触连通块问题的人。BFS也不是不行但你需要额外维护一个队列处理入队出队的顺序对于新手来说容易在“什么时候标记已访问”这个问题上栽跟头。不过话说回来如果你想练BFS这道题也是个很好的载体。而且在实际工程或者面试场景里BFS因为不会递归爆栈有时候反而更稳。我的建议是第一遍用DFS把题目AC了第二遍再尝试用BFS重写一遍。你用同一道题同时练熟两种搜索性价比极高。2.2 四方向的意义以及方向数组的正确写法四方向本质上就是上下左右四个移动向量。在二维数组里我们把“向上移动一行”表示为行号减1列号不变把“向下移动一行”表示为行号加1列号不变向左是列号减1向右是列号加1。于是方向数组可以写成int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1};这里dx表示行号的变化量dy表示列号的变化量。两个数组按下标一一对应i0是上i1是下i2是左i3是右。从当前位置(x, y)出发第i个方向的新位置就是(x dx[i], y dy[i])。这个数组看着简单但我在教学生时发现一个很常见的错误有人会把dx和dy的对应关系写错比如写成dx {0, 0, -1, 1}dy {-1, 1, 0, 0}这样一组合方向就变成了左上、右上、下下整个遍历就乱套了。所以写完方向数组之后强烈建议先在草稿纸上把四个方向都手算一遍确认没问题再往下写。另外当题目要求八方向时方向数组就要扩到8个元素除了上下左右还要加上四个斜角方向也就是(x-1, y-1)、(x-1, y1)、(x1, y-1)、(x1, y1)。这一点在后面的变体题里会再次提到。2.3 时间复杂度与空间开销估算这道题的数据范围不大n 和 m 一般不超过100整个网格最多10000个格子。无论用DFS还是BFS每个格子最多被访问一次每次访问只做常数次判断所以时间复杂度是 O(n×m)也就是最坏情况下约10000次操作对任何语言来说都是毫秒级的事。空间方面如果你用递归DFS主要消耗是递归调用栈。最坏情况下如果整个地图全是水且路径像蛇一样盘绕递归深度可能达到 n×m也就是10000层。C默认栈空间通常够用但我后面会提到Python的递归深度限制问题那是新手最容易踩的坑。如果你不想用递归可以选择BFS用队列显式管理状态栈溢出问题就完全不存在了。提示在动手写代码之前先确认数据范围。如果 n 和 m 都到了1000甚至更大递归DFS可能会导致栈溢出这时候BFS或手写栈的迭代DFS会更安全。USACO白银组这道题数据量很小用递归没问题但养成先看范围的习惯非常重要。3. 完整代码与逐段拆解3.1 C实现附注释我用C写一版可以直接提交的完整代码并配上逐段注释#include bits/stdc.h using namespace std; const int MAXN 105; int n, m; char grid[MAXN][MAXN]; // 四个方向上、下、左、右 int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; void dfs(int x, int y) { // 标记当前格子已经访问过避免重复计数 grid[x][y] .; for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; // 越界检查新位置必须在地图范围内 if (nx 0 || nx n || ny 0 || ny m) continue; // 如果新位置是水则继续递归扩散 if (grid[nx][ny] W) { dfs(nx, ny); } } } int main() { cin n m; // 直接用字符串读入整行 for (int i 0; i n; i) { cin grid[i]; } int ans 0; for (int i 0; i n; i) { for (int j 0; j m; j) { // 找到一块还没被访问过的水说明发现了新池塘 if (grid[i][j] W) { ans; dfs(i, j); } } } cout ans endl; return 0; }这段代码的思路和我上面说的一模一样。主循环负责“发现新大陆”也就是找到还没被访问过的水格子DFS负责“占领全岛”也就是把这个水格子所属的整个池塘都标记成陆地。两者配合每调用一次DFS就说明存在一个池塘所以答案就是DFS被调用的次数。这里有个非常重要的细节标记操作必须放在进入DFS后的第一件事也就是grid[x][y] .;。如果你在递归回退时才标记或者忘记标记会导致同一个格子被反复访问轻则无限递归重则直接栈溢出。这一点怎么强调都不为过。3.2 关键细节读入、标记、递归边界读入环节有个小知识点。如果你用cin grid[i]它会一次性把一整行字符串读入不包含换行符所以不需要额外处理行尾的\n。但如果你用的是scanf记得用%s而不是%c否则你得手动处理换行和空格。很多从C语言转过来的选手容易在这里卡住。关于标记我上面用的是“直接修改地图”也就是把访问过的W改成.。这样做的好处是不用额外开一个visited数组省空间代码也简洁。缺点是它改变了原始输入数据如果后面还需要用到原始地图就不能这么做。在USACO这类竞赛题里输入数据用完即弃所以这个方案完全可行。另一种做法是开一个布尔数组vis初始为false访问时置为true两种写法等价选自己习惯的就好。递归边界其实包含两层一层是数组越界也就是新的坐标不在0 x n和0 y m范围内直接跳过另一层是地形限制也就是新坐标不是W也直接跳过。这两个条件必须同时满足才能继续递归。有些新手会把越界检查放在递归函数开头也可以但我个人更推荐在循环里判断逻辑更清晰。3.3 Python版本与性能注意点如果你平时用Python刷题代码可以写成这样import sys sys.setrecursionlimit(1 25) def solve(): input sys.stdin.readline n, m map(int, input().split()) grid [list(input().strip()) for _ in range(n)] directions [(-1, 0), (1, 0), (0, -1), (0, 1)] def dfs(x, y): grid[x][y] . for dx, dy in directions: nx, ny x dx, y dy if 0 nx n and 0 ny m and grid[nx][ny] W: dfs(nx, ny) ans 0 for i in range(n): for j in range(m): if grid[i][j] W: ans 1 dfs(i, j) print(ans) if __name__ __main__: solve()这里有一行必须保留sys.setrecursionlimit(1 25)。Python默认的递归深度限制是1000层而这张地图最多可能有10000个格子如果整个地图全是水递归深度会超过1000不加这行直接Runtime Error。这也是Python选手做DFS题最容易犯的错。另外Python读入时用了strip()它会去掉字符串两端的空白字符包括行尾换行。因为题目保证每行只有W和.所以strip()是安全的。如果地图里有空格类字符就要谨慎使用。4. 实战中的常见问题与调试技巧4.1 我最常看到的几个WA原因第一类是方向数组写错。这个前面提过了dx和dy的下标对应关系不对或者顺序与自己预想的不一致会导致搜索范围歪掉。记得写完方向数组后用一个枚举测试验证比如从(1, 1)出发四个新坐标分别应该是(0, 1)、(2, 1)、(1, 0)、(1, 2)。第二类是越界检查写漏。有时候你会把检查写成if (nx 0 || ny 0 || nx n || ny m)注意如果数组大小是 n 行 m 列合法范围是0 nx n和0 ny m。nx n这种写法会导致当nx恰好等于n时没有越界但实际已经越界了。这个细节在边界格子上特别容易出现。第三类是标记时机不对。我之前见过一个同学把标记写在DFS递归返回之后结果同一个W被重复入栈最后系统栈爆掉。标记一定要在“进入一个格子时”立刻做而不是“离开一个格子时”做。这就像进屋先锁门防止后面的人再进来。第四类是读入问题。有的同学用scanf(%c)读取字符结果换行符和空格都被当作字符处理了地图数据全是乱的。如果坚持用scanf读取一行字符串用%s最省事如果逐字符读取记得用scanf( %c, grid[i][j])前面的空格会跳过任何空白字符。4.2 调试与测试数据构造刷USACO这类题目你光靠样例测是不够的。一道搜索题我一般会构造以下几类测试数据来验证代码全是水或者全是陆地分别应该输出1和0。只有一行或只有一列用来验证横着排和竖着排的连通情况。斜对角相邻的水格子用来验证四方向到底有没有写对。地图四角分别放一个水格子用来验证边界判断。举个例子输入1 5 W.W.W四个方向的连通规则下三个W各自独立答案应该是3。如果代码输出1说明你把中间隔开的.也当成连通了大概率是方向数组或边界判断出了问题。再比如3 3 W.. .W. ..W三个W各自都在对角线上四方向下它们互不相邻答案应该是3。如果输出1说明你很可能用了八方向或者方向数组写歪了。4.3 常见问题速查表现象可能原因解决方案答案比预期大每次遇到W都计数但没标记导致同一池塘被多次统计确认进入DFS后立即标记答案比预期小方向数组写错水格子被错误连通逐个验证方向移动是否正确程序无限递归或崩溃没有标记已访问或标记得太晚检查标记语句位置确保在递归前执行Python报栈溢出递归深度超过默认限制增加sys.setrecursionlimit读入后地图数据显示不对逐字符读取时吞掉了换行符改用整行字符串读取或用%s边界格子导致越界越界判断用错下标边界确认 nx 0还有一个小技巧当你实在找不到错在哪时把地图打印出来手动模拟一次DFS观察每个格子被访问的顺序很快就能定位到问题。我当年的习惯是写一个调试用函数每次标记格子后把整个地图输出一遍看扩散过程是否符合预期。虽然慢但对新手理解搜索过程非常有帮助。5. 这题做完之后还能往哪走5.1 四方向到八方向只差一个循环USACO有一道更经典的原题叫Lake Counting规则和这题几乎一样唯一区别就是八方向八个相邻方向上的水也算同一池塘。这时方向数组就变成int dx[8] {-1, -1, -1, 0, 0, 1, 1, 1}; int dy[8] {-1, 0, 1, -1, 1, -1, 0, 1};主逻辑一行都不用改只换方向数组代码就能AC。这种从四方向改成八方向的操作是一个极好的练习能让你深刻理解“方向数组就是搜索空间的定义”这个核心思想。我建议每个刷完四方向版的人都顺手把八方向版也写了连题都不用换直接改参数五分钟搞定但这五分钟会帮你建立很强的迁移能力。5.2 从数池塘到数岛屿同类问题地图连通块计数这个模型在算法题里随处可见。比如LeetCode第200题“岛屿数量”本质就是数四方向连通块只是把水换成了陆地还有统计最大连通块面积、统计周长、给连通块编号染色、判断两个点是否连通等等全都是在洪水填充这个框架上做小改动。刷题的时候你会发现一个普遍规律USACO白银组很多题的核心模型都是相通的。今天你花半小时把这题吃透后面遇到网格迷宫、连通区域统计、甚至带障碍的搜索题都会觉得思路顺很多。这道题表面上是“数池塘”实际上是在练一个你之后几百道题都要用的基本功。5.3 这道题对后续USACO刷题的意义从USACO的晋级路线来看白银组只是开始后面还有黄金组和铂金组。但不管哪个组搜索都是最底层的能力。你之后学最短路、最小生成树、动态规划很多问题最终都要落到“遍历状态”上而DFS/BFS就是你遍历状态的基础工具。我个人的体会是与其急着去刷难题不如把这道数池塘题作为一种“手感校准器”。每次遇到搜索相关的新知识点比如记忆化搜索、剪枝、迭代加深都可以拿这个题来验证自己的理解有没有跑偏。它就像运动员的热身动作简单但每次做都有价值。最后再分享一个做题习惯我刷USACO这么多年发现真正拉开差距的不是会不会做难题而是基础题能不能一遍写对。这道数池塘题看着人畜无害但如果你能在五分钟内无bug写出四方向版本并一次通过说明你的搜索基本功已经相当扎实了。别跳过基础题直接啃硬骨头该练的基本功一道都跑不了。
USACO白银组真题：数池塘与DFS连通块计数深度解析
USACO的白银组历来是个分水岭过了铜牌之后很多人第一次在这里感到“算法题突然变得不那么直给了”。2005年3月这套白银组真题放在今天看难度不算高但它有一道题非常典型几乎是把“连通块计数”这个考点焊死在了入门搜索的必经之路上——就是网络热词里提到的“数池塘四方向”。这道题也叫Lake Counting的一个变体很多新手第一次接触DFS/BFS就是从它开始的。我自己刷这道题的时候还在上大学当时觉得“这不就是数有几个水坑嘛”结果一写就翻车要么死循环要么边界溢出要么方向数组里四个方向写错两个。后来带学生刷USACO发现大家在同一个地方踩的坑几乎一模一样。所以这篇就把2005年3月白银组的这道数池塘题彻底拆开讲从题目理解、解法选型、代码实现到调试排查一次说清楚。适合刚过铜牌、准备冲白银组的人也适合那些想用一道题把DFS连通块彻底搞懂的人。1. 2005年3月白银组这道题到底在考什么1.1 题目长什么样原题描述很直白给你一个 n 行 m 列的网格地图每个格子里只有两种状态一种是水用字符W表示另一种是陆地用.表示。所谓“池塘”就是由若干个相邻的水格子连成的一个区域。注意这里的相邻只算上下左右四个方向也就是四连通斜对角方向上的水格子不算连在一起。题目要求你输出这张地图里总共有多少个池塘。光看文字可能不够直观我构造一个简单的测试数据输入 4 5 .W.W. .W.W. .W.W. ....W 输出 3在这个例子里第一列和第二列各有三行是连续的W它们各自构成一个池塘最右下角那个单独的W虽然离左边那几个水格子很近但斜对角不算连通所以它自己也是一个池塘。最后答案是3。这个题输入方式也很传统第一行两个整数 n 和 m接下来 n 行是地图字符串字符之间没有空格。输出就一个整数池塘数量。1.2 考点拆解连通块计数与洪水填充这道题的本质是把一个二维网格里所有“连在一起的水格子”划分成若干个组然后数组的个数。在算法领域这个操作叫连通块计数实现它的经典手法叫洪水填充Flood Fill你可以想象成往一个水坑里倒墨水墨水会自动沿着连通的格子扩散直到把这个水坑全部染色然后再去下一个水坑。USACO把这道题放在白银组是有道理的。它不会像铜牌题那样直接告诉你“请用搜索”而是把搜索藏在一个日常场景里。你需要自己想到每个W都可能是某个池塘的起点从一个起点出发把所有相邻的W全部访问并标记掉下次再遇到还没标记的W就说明发现了一个新池塘。能想明白这一步银组入门级的搜索题基本上就通了一半。另外这个题目还有一个容易被忽略的点它明确写了“四方向”。USACO里还有一道更经典的八方向版本也就是行差和列差绝对值不超过1都算相邻。四方向版本相对简单但它更干净地突出了“方向数组”这个基础概念。你在做题时最好先确认清楚题目要求是四方向还是八方向这一步搞错后面全白写。2. 解法选型为什么建议新手从DFS入手2.1 DFS与BFS的取舍在地图类的连通块问题上DFS深度优先搜索和BFS广度优先搜索都能做核心思想是一样的找到一个水格子就沿着它一路把所有连通的水格子都找出来并标记。区别只在于扩散的顺序DFS是“一条路走到黑”BFS是“一圈一圈往外扩”。我个人的建议是这道题优先用DFS。原因很实际代码量少理解成本低。一个递归函数加上一个方向数组加起来不到二十行非常适合第一次接触连通块问题的人。BFS也不是不行但你需要额外维护一个队列处理入队出队的顺序对于新手来说容易在“什么时候标记已访问”这个问题上栽跟头。不过话说回来如果你想练BFS这道题也是个很好的载体。而且在实际工程或者面试场景里BFS因为不会递归爆栈有时候反而更稳。我的建议是第一遍用DFS把题目AC了第二遍再尝试用BFS重写一遍。你用同一道题同时练熟两种搜索性价比极高。2.2 四方向的意义以及方向数组的正确写法四方向本质上就是上下左右四个移动向量。在二维数组里我们把“向上移动一行”表示为行号减1列号不变把“向下移动一行”表示为行号加1列号不变向左是列号减1向右是列号加1。于是方向数组可以写成int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1};这里dx表示行号的变化量dy表示列号的变化量。两个数组按下标一一对应i0是上i1是下i2是左i3是右。从当前位置(x, y)出发第i个方向的新位置就是(x dx[i], y dy[i])。这个数组看着简单但我在教学生时发现一个很常见的错误有人会把dx和dy的对应关系写错比如写成dx {0, 0, -1, 1}dy {-1, 1, 0, 0}这样一组合方向就变成了左上、右上、下下整个遍历就乱套了。所以写完方向数组之后强烈建议先在草稿纸上把四个方向都手算一遍确认没问题再往下写。另外当题目要求八方向时方向数组就要扩到8个元素除了上下左右还要加上四个斜角方向也就是(x-1, y-1)、(x-1, y1)、(x1, y-1)、(x1, y1)。这一点在后面的变体题里会再次提到。2.3 时间复杂度与空间开销估算这道题的数据范围不大n 和 m 一般不超过100整个网格最多10000个格子。无论用DFS还是BFS每个格子最多被访问一次每次访问只做常数次判断所以时间复杂度是 O(n×m)也就是最坏情况下约10000次操作对任何语言来说都是毫秒级的事。空间方面如果你用递归DFS主要消耗是递归调用栈。最坏情况下如果整个地图全是水且路径像蛇一样盘绕递归深度可能达到 n×m也就是10000层。C默认栈空间通常够用但我后面会提到Python的递归深度限制问题那是新手最容易踩的坑。如果你不想用递归可以选择BFS用队列显式管理状态栈溢出问题就完全不存在了。提示在动手写代码之前先确认数据范围。如果 n 和 m 都到了1000甚至更大递归DFS可能会导致栈溢出这时候BFS或手写栈的迭代DFS会更安全。USACO白银组这道题数据量很小用递归没问题但养成先看范围的习惯非常重要。3. 完整代码与逐段拆解3.1 C实现附注释我用C写一版可以直接提交的完整代码并配上逐段注释#include bits/stdc.h using namespace std; const int MAXN 105; int n, m; char grid[MAXN][MAXN]; // 四个方向上、下、左、右 int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; void dfs(int x, int y) { // 标记当前格子已经访问过避免重复计数 grid[x][y] .; for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; // 越界检查新位置必须在地图范围内 if (nx 0 || nx n || ny 0 || ny m) continue; // 如果新位置是水则继续递归扩散 if (grid[nx][ny] W) { dfs(nx, ny); } } } int main() { cin n m; // 直接用字符串读入整行 for (int i 0; i n; i) { cin grid[i]; } int ans 0; for (int i 0; i n; i) { for (int j 0; j m; j) { // 找到一块还没被访问过的水说明发现了新池塘 if (grid[i][j] W) { ans; dfs(i, j); } } } cout ans endl; return 0; }这段代码的思路和我上面说的一模一样。主循环负责“发现新大陆”也就是找到还没被访问过的水格子DFS负责“占领全岛”也就是把这个水格子所属的整个池塘都标记成陆地。两者配合每调用一次DFS就说明存在一个池塘所以答案就是DFS被调用的次数。这里有个非常重要的细节标记操作必须放在进入DFS后的第一件事也就是grid[x][y] .;。如果你在递归回退时才标记或者忘记标记会导致同一个格子被反复访问轻则无限递归重则直接栈溢出。这一点怎么强调都不为过。3.2 关键细节读入、标记、递归边界读入环节有个小知识点。如果你用cin grid[i]它会一次性把一整行字符串读入不包含换行符所以不需要额外处理行尾的\n。但如果你用的是scanf记得用%s而不是%c否则你得手动处理换行和空格。很多从C语言转过来的选手容易在这里卡住。关于标记我上面用的是“直接修改地图”也就是把访问过的W改成.。这样做的好处是不用额外开一个visited数组省空间代码也简洁。缺点是它改变了原始输入数据如果后面还需要用到原始地图就不能这么做。在USACO这类竞赛题里输入数据用完即弃所以这个方案完全可行。另一种做法是开一个布尔数组vis初始为false访问时置为true两种写法等价选自己习惯的就好。递归边界其实包含两层一层是数组越界也就是新的坐标不在0 x n和0 y m范围内直接跳过另一层是地形限制也就是新坐标不是W也直接跳过。这两个条件必须同时满足才能继续递归。有些新手会把越界检查放在递归函数开头也可以但我个人更推荐在循环里判断逻辑更清晰。3.3 Python版本与性能注意点如果你平时用Python刷题代码可以写成这样import sys sys.setrecursionlimit(1 25) def solve(): input sys.stdin.readline n, m map(int, input().split()) grid [list(input().strip()) for _ in range(n)] directions [(-1, 0), (1, 0), (0, -1), (0, 1)] def dfs(x, y): grid[x][y] . for dx, dy in directions: nx, ny x dx, y dy if 0 nx n and 0 ny m and grid[nx][ny] W: dfs(nx, ny) ans 0 for i in range(n): for j in range(m): if grid[i][j] W: ans 1 dfs(i, j) print(ans) if __name__ __main__: solve()这里有一行必须保留sys.setrecursionlimit(1 25)。Python默认的递归深度限制是1000层而这张地图最多可能有10000个格子如果整个地图全是水递归深度会超过1000不加这行直接Runtime Error。这也是Python选手做DFS题最容易犯的错。另外Python读入时用了strip()它会去掉字符串两端的空白字符包括行尾换行。因为题目保证每行只有W和.所以strip()是安全的。如果地图里有空格类字符就要谨慎使用。4. 实战中的常见问题与调试技巧4.1 我最常看到的几个WA原因第一类是方向数组写错。这个前面提过了dx和dy的下标对应关系不对或者顺序与自己预想的不一致会导致搜索范围歪掉。记得写完方向数组后用一个枚举测试验证比如从(1, 1)出发四个新坐标分别应该是(0, 1)、(2, 1)、(1, 0)、(1, 2)。第二类是越界检查写漏。有时候你会把检查写成if (nx 0 || ny 0 || nx n || ny m)注意如果数组大小是 n 行 m 列合法范围是0 nx n和0 ny m。nx n这种写法会导致当nx恰好等于n时没有越界但实际已经越界了。这个细节在边界格子上特别容易出现。第三类是标记时机不对。我之前见过一个同学把标记写在DFS递归返回之后结果同一个W被重复入栈最后系统栈爆掉。标记一定要在“进入一个格子时”立刻做而不是“离开一个格子时”做。这就像进屋先锁门防止后面的人再进来。第四类是读入问题。有的同学用scanf(%c)读取字符结果换行符和空格都被当作字符处理了地图数据全是乱的。如果坚持用scanf读取一行字符串用%s最省事如果逐字符读取记得用scanf( %c, grid[i][j])前面的空格会跳过任何空白字符。4.2 调试与测试数据构造刷USACO这类题目你光靠样例测是不够的。一道搜索题我一般会构造以下几类测试数据来验证代码全是水或者全是陆地分别应该输出1和0。只有一行或只有一列用来验证横着排和竖着排的连通情况。斜对角相邻的水格子用来验证四方向到底有没有写对。地图四角分别放一个水格子用来验证边界判断。举个例子输入1 5 W.W.W四个方向的连通规则下三个W各自独立答案应该是3。如果代码输出1说明你把中间隔开的.也当成连通了大概率是方向数组或边界判断出了问题。再比如3 3 W.. .W. ..W三个W各自都在对角线上四方向下它们互不相邻答案应该是3。如果输出1说明你很可能用了八方向或者方向数组写歪了。4.3 常见问题速查表现象可能原因解决方案答案比预期大每次遇到W都计数但没标记导致同一池塘被多次统计确认进入DFS后立即标记答案比预期小方向数组写错水格子被错误连通逐个验证方向移动是否正确程序无限递归或崩溃没有标记已访问或标记得太晚检查标记语句位置确保在递归前执行Python报栈溢出递归深度超过默认限制增加sys.setrecursionlimit读入后地图数据显示不对逐字符读取时吞掉了换行符改用整行字符串读取或用%s边界格子导致越界越界判断用错下标边界确认 nx 0还有一个小技巧当你实在找不到错在哪时把地图打印出来手动模拟一次DFS观察每个格子被访问的顺序很快就能定位到问题。我当年的习惯是写一个调试用函数每次标记格子后把整个地图输出一遍看扩散过程是否符合预期。虽然慢但对新手理解搜索过程非常有帮助。5. 这题做完之后还能往哪走5.1 四方向到八方向只差一个循环USACO有一道更经典的原题叫Lake Counting规则和这题几乎一样唯一区别就是八方向八个相邻方向上的水也算同一池塘。这时方向数组就变成int dx[8] {-1, -1, -1, 0, 0, 1, 1, 1}; int dy[8] {-1, 0, 1, -1, 1, -1, 0, 1};主逻辑一行都不用改只换方向数组代码就能AC。这种从四方向改成八方向的操作是一个极好的练习能让你深刻理解“方向数组就是搜索空间的定义”这个核心思想。我建议每个刷完四方向版的人都顺手把八方向版也写了连题都不用换直接改参数五分钟搞定但这五分钟会帮你建立很强的迁移能力。5.2 从数池塘到数岛屿同类问题地图连通块计数这个模型在算法题里随处可见。比如LeetCode第200题“岛屿数量”本质就是数四方向连通块只是把水换成了陆地还有统计最大连通块面积、统计周长、给连通块编号染色、判断两个点是否连通等等全都是在洪水填充这个框架上做小改动。刷题的时候你会发现一个普遍规律USACO白银组很多题的核心模型都是相通的。今天你花半小时把这题吃透后面遇到网格迷宫、连通区域统计、甚至带障碍的搜索题都会觉得思路顺很多。这道题表面上是“数池塘”实际上是在练一个你之后几百道题都要用的基本功。5.3 这道题对后续USACO刷题的意义从USACO的晋级路线来看白银组只是开始后面还有黄金组和铂金组。但不管哪个组搜索都是最底层的能力。你之后学最短路、最小生成树、动态规划很多问题最终都要落到“遍历状态”上而DFS/BFS就是你遍历状态的基础工具。我个人的体会是与其急着去刷难题不如把这道数池塘题作为一种“手感校准器”。每次遇到搜索相关的新知识点比如记忆化搜索、剪枝、迭代加深都可以拿这个题来验证自己的理解有没有跑偏。它就像运动员的热身动作简单但每次做都有价值。最后再分享一个做题习惯我刷USACO这么多年发现真正拉开差距的不是会不会做难题而是基础题能不能一遍写对。这道数池塘题看着人畜无害但如果你能在五分钟内无bug写出四方向版本并一次通过说明你的搜索基本功已经相当扎实了。别跳过基础题直接啃硬骨头该练的基本功一道都跑不了。
