企业官网建设流程全解析

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^5，Flood 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) { queue<pair<int, 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 题岛屿数量就是 P1596 的四方向版本，695 题岛屿最大面积就是在 Flood Fill 过程中多维护一个计数器。面试时如果你能从这道题一路讲到图像连通域标记的工程差异，会比单纯背题让人印象深刻得多。

5.3 给你留一个练手方向

我建议你拿到这道题后不要只写一版就收工，而是至少连写三个版本：DFS、BFS、带 visited 数组的版本。然后把 DFS 版改成四方向连通，去跑通 LeetCode 200；再把 BFS 版改成统计面积，去跑通 LeetCode 695。三遍下来，Flood Fill 基本上就焊死在你的手上了。

从我个人刷题的习惯来说，P1596 这类基础题最忌讳的就是"AC 完就翻篇"。真正把一道水题吃透，往往比稀里糊涂刷十道新题更有效。我当年花了一个晚上在这道题上反复改三种写法，后来做岛屿系列和图像处理相关的项目，几乎没有再为连通域的框架问题卡过壳。这也是为什么到现在我偶尔看到有人问这题，还会很乐意再讲一遍——它真的是整个连通块问题家族的钥匙。