1. 先把这道题看透P1596到底在考察什么1.1 题目翻译与核心考点拿到这个标题很多人会愣一下P1596zhaochitang前面是洛谷题号后面一串拼音其实就是找池塘三个字的拼音对应的是 USACO 2006 年 10 月的一道经典铜组题 Lake Counting洛谷上的中文翻译叫湖泊计数。题面讲的是农夫约翰的农场下了一场大雨低洼处积了水W表示水.表示干地只要两个水格子之间上下左右或者斜对角相邻就算同一片湖泊最后要求统计整个农场上一共有多少个湖泊。听起来很简单但这道题是连通块计数这个算法分支里最典型的入门题无数人从它开始接触 Flood Fill也有无数人第一次 WA 就是栽在八方向三个字上。简单说这道题就干一件事数连通块。但数连通块有一个非常容易翻车的细节——八方向连通。四个正交方向上、下、左、右是最常见的直觉很多人一看到相邻就下意识只写四个方向样例数据里碰巧没有对角线相连的情况于是本地一跑全对一交上去 WA 一片。如果你能在做这道题之前就意识到斜对角也算相邻那说明你对连通性的理解已经到位了。再往深一层说这道题背后是 Flood Fill 泛滥填充算法的思想和画图软件里的魔术棒选区、游戏里的踩地图、图像识别里的连通域标记用的都是同一套东西。所以我会花点篇幅把套路讲透后面你遇到任何连通块变体回头再看这题都会觉得很轻松。1.2 数据范围才是定心丸先看数据范围N 和 M 都限制在 1 到 100。这是整道题里最容易被忽略、但最值得先看的信息。100×100 的格子总数最多一万个也就是说从任意起点出发的遍历最坏情况也就是把全图一万个点都扫一遍两层嵌套循环枚举全图同样是 O(10^4) 量级总体时间复杂度 O(NM)在任何一个主流 OJ 的时限下都是瞬间出结果的。竞赛里有个非常重要的习惯叫先看范围再定算法。如果这道题的 N、M 开到 10^5Flood Fill 就不能无脑用了得考虑并查集离线处理、线段树扫描线之类的方案但在 100×100 的规模下一个简单粗暴的 DFS 就是正解不需要任何花活。我见过有人非要在这种水题上写并查集把简单问题复杂化结果反而写错这就是没想清楚数据范围的意义。这道题的定心丸性质就在于你只需要保证算法复杂度是 O(NM) 级别其他什么都好说。2. 核心思维转变不要找湖泊要划掉湖泊2.1 从人在棋盘上连线到油漆桶倒下去第一次做这类题的人最容易陷入的误区是试图在扫描过程中实时判断哪些W应该合并成一组。比如有人会想遇到一个W就看看左边和上边有没有水有就并入那个湖——这其实已经是并查集的思路了。按行扫描的话很快会遇到一个非常恶心的情况左右两块水中间隔了半行干地结果下半行某处又连起来了你之前的分类全部作废还得回头修改归属关系。正确的心智模型是反过来的你不去分辨每个水格属于哪个湖而是找到一个还没处理过的水格从这里往八个方向扩散把能连通的所有水全部划掉划完一片心里记一个数。这个动作重复下去直到整个场地没有任何水剩下。你划了几次就有几片湖。这个划掉的动作就是 Flood Fill 的本质。用生活类比来说这就像你在画图软件里拿油漆桶往图上倒颜料颜料顺着颜色相近的像素自动蔓延到整个连通的区域。你不需要预先知道这个区域有多大、形状多奇怪只要给一个种子点扩散过程自动搞定一切。P1596 里的每次dfs调用或者每个bfs队列的启动就是一次倒颜料的过程。2.2 原地修改还是 visited 数组划掉在代码层面有两种实现方式第一种是直接在原始数组上把W改成.。优点是零额外空间、代码最短缺点是会破坏原始数据。第二种是另开一个bool visited[N][M]访问过就标true优点是不破坏原始地图缺点是多花一万个 bool 的空间以及每次判断都要多看一眼 visited。在 P1596 这道题里输入地图用完就扔后面没有任何地方需要重新读取原始水迹所以原地修改是最干净的选择。当然就本题的数据量来说开 visited 数组也不会有任何性能问题纯粹是代码风格取舍。我个人更推荐原地修改能少一个数组就少一个数组找 bug 的时候要检查的东西就少一件。提示原地修改时把格子改成什么字符其实随你.、#、V都可以只要别改成W就行。关键是把已处理这个状态可靠地记录下来。2.3 方向数组怎么写才不出错八方向连通的坐标偏移量最稳妥的写法是硬编码方向数组int dx[] {-1, -1, -1, 0, 0, 1, 1, 1}; int dy[] {-1, 0, 1, -1, 1, -1, 0, 1};八个方向依次是左上、上、右上、左、右、左下、下、右下。这样写的好处是一目了然检查的时候用肉眼就能核对有没有漏方向。不想背方向数组的话也可以用 -1、0、1 的双重循环生成for (int u -1; u 1; u) { for (int v -1; v 1; v) { if (u 0 v 0) continue; // 这里处理 (x u, y v) } }双重循环的优点是不会漏方向缺点是多了一次(0,0)自环判断。其实即使不跳过(0,0)因为当前格子已经被划掉了不会真的死循环但白白多一次无用操作所以顺手写掉continue更规范。3. DFS 与 BFS 双版本实现以及我的选择理由3.1 DFS 版递归向下沉DFS 的思路很直白从一个合法起点出发标记当前格然后 8 个方向挨个看碰到没处理过的水就直接递归进去。完整代码如下#include iostream using namespace std; const int MAXN 105; char grid[MAXN][MAXN]; int n, m; int dx[] {-1, -1, -1, 0, 0, 1, 1, 1}; int dy[] {-1, 0, 1, -1, 1, -1, 0, 1}; void dfs(int x, int y) { grid[x][y] .; // 划掉当前水格 for (int i 0; i 8; 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 \n; return 0; }主循环里每发现一个还没被划掉的W就先ans再从它开始把整片湖划掉。这样这个W绝不会在后面的扫描里再被当作新湖的起点也不会被别的湖重复处理。整份代码就这么点信息量核心逻辑其实只有dfs函数内部的十来行。3.2 BFS 版用队列平铺扩散BFS 不使用递归而是维护一个队列一层一层向外扩散#include iostream #include queue using namespace std; const int MAXN 105; char grid[MAXN][MAXN]; int n, m; int dx[] {-1, -1, -1, 0, 0, 1, 1, 1}; int dy[] {-1, 0, 1, -1, 1, -1, 0, 1}; void bfs(int sx, int sy) { queuepairint, int q; q.push({sx, sy}); grid[sx][sy] .; while (!q.empty()) { auto cur q.front(); q.pop(); int x cur.first, y cur.second; for (int i 0; i 8; 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) { grid[nx][ny] .; q.push({nx, ny}); } } } }注意我在这里把标记动作放在入队之前执行而不是出队时才标记。这个顺序问题我第 4 节会展开讲这里先说结论入队即标记能避免同一个格子被多个邻居重复塞进队列保证每个格子最多入队一次。3.3 为什么多数情况下我更推荐 DFS这两版代码的正确性和复杂度完全等价选哪个纯粹是工程习惯。我的个人倾向是 DFS理由有三个第一代码量小。不用 include queue不用担心pair的写法递归天然不需要维护额外容器。第二思路直观。递归调用栈本身就模拟了从起点一路深入再回头的探索过程和脑子里想象的蔓延过程一致。第三本题递归深度安全。最坏情况整个场地 10000 个格子全是水且连成蛇形递归深度也就是 10000。C 默认栈空间有 8MB每层递归消耗几十字节完全不会爆栈。注意如果你用 Python 写 DFS必须在开头加import sys; sys.setrecursionlimit(1000000)。Python 默认递归上限是 1000而这个场地最多能形成 10000 层的递归链不加限制会直接 RecursionError。很多人第一次在看似简单的题上翻车就是栽在这个语言默认限制上。BFS 则完全没有递归深度问题因为用的是显式队列调用栈上只留一个函数帧。这也是 BFS 在工程场景里更常见的原因。如果你以后打算写图像处理、地图寻路这类程序BFS 还顺带能算最短路径DFS 做不了这个。理解了这一点你就能明白为什么我说高频场景用 BFS竞赛刷题用 DFS。3.4 Python 完整版顺手给一份 Python 的 BFS 版本适合 Python 党直接拿去用from collections import deque n, m map(int, input().split()) grid [list(input().strip()) for _ in range(n)] dx [-1, -1, -1, 0, 0, 1, 1, 1] dy [-1, 0, 1, -1, 1, -1, 0, 1] def bfs(sx, sy): q deque() q.append((sx, sy)) grid[sx][sy] . while q: x, y q.popleft() for i in range(8): nx, ny x dx[i], y dy[i] if 0 nx n and 0 ny m and grid[nx][ny] W: grid[nx][ny] . q.append((nx, ny)) ans 0 for i in range(n): for j in range(m): if grid[i][j] W: ans 1 bfs(i, j) print(ans)Python 版 BFS 不需要调节递归上限省心。如果你非要写 Python DFS记得先在文件最顶上把 recursionlimit 抬上去。4. 实战中踩过的坑读入、标记、边界一个都别漏4.1 字符读入的空格陷阱这道题的官方样例长这样10 12 W........WW. .WWW.....WWW ....WW...WW. .........WW. .........W.. ..W......W.. .W.W.....WW. W.W.W.....W. .W.W......W. ..W.......W.注意每行字符串里没有任何空格。C 选手用cin grid[i]读整行没问题scanf用%s也没问题但千万别用%c一个字符一个字符读那样会把行尾的换行符一并读进来导致整个棋盘错位。Python 选手用input()读整行时记得用strip()去掉行尾换行再list()转成字符数组。有些同学习惯用split()以为字符之间有空行一试就发现读进来全是一个个单独的整串半天没反应过来。这算是所有字符矩阵题的经典坑。我的习惯是看到输入样例后先敲一个小的本地测试用例确认读入层面没问题再写主逻辑这样能把读入错误和算法错误两类问题彻底隔离开定位 bug 快得多。4.2 标记时机出队标记还是入队标记BFS 新手最常见的 bug 是出队才标记while (!q.empty()) { auto cur q.front(); q.pop(); // 如果在这里才标记同一个格子可能被多个邻居重复入队 ... }这样写不是不能 AC但同一个W可能被好几个邻居先后入队队列里会堆积大量重复状态。在小数据上无感但在更大规模的问题上队列长度可能膨胀好几倍白白浪费时间和内存。正确姿势是入队时立刻标记grid[nx][ny] .; q.push({nx, ny});这样每个格子最多被入队一次整个 BFS 的复杂度严格 O(NM)。养成这个习惯后后面遇到矩阵迷宫、状态空间搜索的题你会少踩很多坑。这算是从 P1596 这种小水题里带出来的一项长效收益。4.3 边界判断的顺序真的会决定生死越界判断必须放在数组访问之前if (nx 0 || nx n || ny 0 || ny m) continue; if (grid[nx][ny] W) { ... }C 的||和都是短路求值的所以第一个判断只要为true后面的数组访问根本不会执行。但如果你手滑写成if (grid[nx][ny] W nx 0 nx n ny 0 ny m)那么当nx -1时grid[-1][ny]就已经是越界访问了后面的所有判断都白搭。轻则读到随机内存导致 WA重则直接段错误。这个错误在棋盘类题目里出现频率极高我至少见过三个同学在讨论区求助时贴出来的代码都是这个问题。提示Python 因为支持负索引这个坑更隐蔽——grid[-1][ny]在语法上完全合法访问的是最后一行程序不会报错但结果错得莫名其妙。所以 Python 选手更要坚持先判范围再访问的顺序。4.4 从 1 开始编号还是从 0 开始编号很多棋盘题喜欢把地图存成从 1 开始编号的二维数组四周留一圈边界字符这样能省掉所有越界判断。P1596 也可以这么干把数组开成MAXN 2读入时偏移到 1 开始越界检查直接消失因为边界一圈都是非W字符。这个技巧在迷宫类题目里尤其好用。不过 P1596 本身只有 8 个方向手写越界判断也就一行两种方案的代码量差不了多少。我的建议是用你熟悉的那个方案不要临时变换风格。做竞赛题最怕的不是某个写法不好而是中途换思路导致心态不稳。4.5 样例通过后的自测方法P1596 的样例答案是 3能过样例说明基本框架没问题但样例只能证明你的代码能跑不能证明思路是对的。我每次做完都会额外构造几组极限数据自测全W的 1×1 场地答案应该是 1全.的场地答案应该是 0一条斜线连通的 100×100 场地答案应该是 1专门用来测八方向两个对角相隔一格的水块中间隔着干地答案应该是 2。这些自测用例的价值不是跑对就行而是逼着你把边角逻辑都想清楚。很多 WA 其实就是脑子里建立的模型和真实数据不一致自测就是在校准模型。5. 从湖泊计数往远处走连通域标记与派生问题5.1 这道题在图像处理里的真面目P1596 的底层模型就是二值图像的连通域标记。把W当成前景像素.当成背景像素数湖泊就是数一张二值图里有多少块连在一起的前景区域。工业界的常用做法不外乎三类基于 DFS/BFS 的种子填充、基于并查集的等价类合并、以及专门为超大图设计的两遍扫描算法Two-pass Connected Component Labeling。前两种你在竞赛里就能见到第三种是典型的工程问题。一张 1920×1080 的照片拆成二值图后有大概两百万个像素用递归 DFS 风险很高所以工程代码里几乎都是 BFS 配显式队列或者把整张图拆成小块做两遍扫描再做连通关系合并。思路和 P1596 完全同源只是规模不一样。理解这一点后P1596 的价值就不止是一道练习题了它是你进入图像分割、目标检测、游戏地图处理这些方向的第一个台阶。5.2 常见派生题目一览顺着这道题你可以往上延伸出一串变体变体改动点难度变化岛屿数量LeetCode 200四方向连通更简单岛屿的最大面积LeetCode 695Flood Fill 里顺带维护面积同一难度统计每个湖泊的大小与分布每次 Flood Fill 记录大小同一难度用并查集做连通块计数合并 查父节点不遍历略进阶彩色图的连通域标记状态从单字符变成多标签工程向LeetCode 上的 200 题岛屿数量就是 P1596 的四方向版本695 题岛屿最大面积就是在 Flood Fill 过程中多维护一个计数器。面试时如果你能从这道题一路讲到图像连通域标记的工程差异会比单纯背题让人印象深刻得多。5.3 给你留一个练手方向我建议你拿到这道题后不要只写一版就收工而是至少连写三个版本DFS、BFS、带 visited 数组的版本。然后把 DFS 版改成四方向连通去跑通 LeetCode 200再把 BFS 版改成统计面积去跑通 LeetCode 695。三遍下来Flood Fill 基本上就焊死在你的手上了。从我个人刷题的习惯来说P1596 这类基础题最忌讳的就是AC 完就翻篇。真正把一道水题吃透往往比稀里糊涂刷十道新题更有效。我当年花了一个晚上在这道题上反复改三种写法后来做岛屿系列和图像处理相关的项目几乎没有再为连通域的框架问题卡过壳。这也是为什么到现在我偶尔看到有人问这题还会很乐意再讲一遍——它真的是整个连通块问题家族的钥匙。