与广度优先搜索(BFS)实战：从“红与黑”题解到二维网格遍历模板)
1. 项目概述从“红与黑”到经典算法题的深度解构“红与黑”这个名字乍一听可能让人联想到司汤达的文学名著或是某种艺术风格。但在我们C程序员的世界里尤其是在算法竞赛和面试刷题的语境下它特指一道非常经典的深度优先搜索DFS或广度优先搜索BFS入门题。这道题通常被归类为“Flood Fill”洪水填充算法的基础应用是检验一个程序员是否真正理解递归和搜索思想的绝佳试金石。我从业十多年带过不少新人发现很多朋友在初次接触这类二维网格遍历问题时思路容易混乱代码写得冗长且易错。今天我们就以这道“红与黑”为引子不仅把这道题本身讲透更要把其背后所代表的二维网格搜索问题的通用解题框架、代码优化技巧以及相关的C核心知识串讲一遍。无论你是正在准备蓝桥杯、ACM等算法竞赛的学生还是希望夯实基础的职场新人这篇文章都将为你提供一个清晰、可复现的实战指南。这道题的典型描述是这样的给定一个由字符构成的二维网格其中‘.’代表黑色瓷砖可通行区域‘#’代表红色瓷砖障碍物‘’代表人的起始位置。人只能站在黑色瓷砖上并且可以向上、下、左、右四个方向移动。问题是从起始位置‘’出发最多可以走过多少块黑色瓷砖同一个瓷砖不能重复计算。这本质上就是计算从起点出发在网格中能连通的所有‘.’格子的数量。理解了这一点我们就抓住了问题的核心——图的遍历。2. 核心思路与算法选型为什么是DFS/BFS面对一个二维网格遍历问题我们首先需要确定算法策略。最常见的候选者就是深度优先搜索DFS和广度优先搜索BFS。对于“红与黑”这类连通块计数问题两者在结果上是等价的都能正确计算出连通区域的大小。但在具体实现和思考角度上它们各有侧重。深度优先搜索DFS的核心思想是“一条路走到黑碰壁再回头”。从起点开始选择一个方向前进直到无法继续遇到边界、障碍物或已访问过的格子然后回溯到上一个分岔点尝试其他方向。DFS通常使用递归来实现代码非常简洁直观非常符合人类“探索”的直觉。其空间复杂度主要取决于递归调用栈的深度在最坏情况下比如整个网格都是连通的‘.’栈深度可能达到O(N*M)。对于“红与黑”这种规模的题目通常网格边长在20以内递归栈完全够用。广度优先搜索BFS的核心思想是“层层推进涟漪扩散”。从起点开始将其放入一个队列然后每次从队列中取出一个位置将其所有未访问的相邻可通行位置加入队列。这个过程就像在水面投入一颗石子波纹一圈圈荡开。BFS天然保证了我们是以“从起点开始的最短距离”的顺序来访问每个节点的虽然对于本题来说这个特性不是必需的。BFS通常使用循环和队列如C的queue实现避免了递归可能带来的栈溢出风险对于极端大的网格代码稍显繁琐但结构清晰。如何选择对于“红与黑”这道题我个人更倾向于使用DFS递归解法。原因有三第一代码量小逻辑清晰易于在笔试面试中快速实现第二题目数据范围通常友好无需担心栈溢出第三DFS的递归过程本身就是对“搜索”这一概念最直接的诠释有助于理解回溯思想。当然掌握BFS的写法也同样重要它是解决最短路径等问题的基础。在后续的“常见问题”章节我会给出两种解法的完整代码并进行对比。确定了算法接下来就是设计程序的核心数据结构。我们通常用一个二维的vectorstring或字符数组来存储网格用一个同样大小的二维布尔数组如vectorvectorbool visited来记录每个格子是否已被访问过防止重复计数。方向数组int dirs[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};定义了上下左右四个方向的坐标偏移这是处理网格类问题的标准技巧能让代码避免写四个冗长的if判断。3. 深度优先搜索DFS解法精讲与实现细节让我们聚焦于最常用的DFS递归解法并一步步拆解其中的每一个细节。3.1 数据读取与初始化任何算法的第一步都是正确地读入数据。“红与黑”题目的输入格式虽然可能有微调但大体类似首先输入两个整数W和H分别代表网格的宽度列数和高度行数。当W和H都为0时输入终止。随后输入H行字符串每行包含W个字符描述整个网格。这里有一个初学者极易踩坑的地方行与列的顺序。我们通常习惯用(行索引 列索引)即(i, j)来定位一个格子其中i的范围是[0, H-1]j的范围是[0, W-1]。在读取时外层循环对应行i内层对应列j。同时在遍历寻找起始点‘’时也要注意这个顺序。#include iostream #include vector using namespace std; int main() { int W, H; while (cin W H (W || H)) { // 循环处理多个案例 vectorstring grid(H); int start_i -1, start_j -1; for (int i 0; i H; i) { cin grid[i]; // 读入一行 // 在读入的同时寻找起点避免二次遍历 for (int j 0; j W; j) { if (grid[i][j] ) { start_i i; start_j j; // 将起点也视为可通行的黑色瓷砖通常题目允许 grid[i][j] .; } } } // ... 后续处理 } return 0; }注意有些题目描述中起点‘’本身也算作一块可通行的瓷砖需要在计数时包含。所以我们在找到起点后可以将其字符临时改为‘.’方便统一处理。当然也可以在DFS函数中单独为‘’位置做判断。3.2 DFS递归函数的编写这是整个程序的核心。递归函数dfs(i, j)的含义是从位置(i, j)出发统计能到达的黑色瓷砖数量并返回这个值。函数设计要点返回值int表示从当前点出发能访问到的瓷砖总数包含当前点。参数当前坐标(i, j)。终止条件递归基当前点越界、是障碍物‘#’、或者已经被访问过。此时应返回0。标记访问一旦进入一个合法的、未访问的点立即将其标记为已访问。这是防止无限递归的关键。递归探索向四个方向分别进行探索并将子问题的结果累加。累加返回当前点的贡献是1自己这块砖加上所有方向探索结果的总和。// 假设 grid 和 visited 是全局变量或在类中可访问 vectorstring grid; vectorvectorbool visited; int H, W; int dirs[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右 int dfs(int i, int j) { // 1. 边界检查与合法性检查 if (i 0 || i H || j 0 || j W) return 0; if (grid[i][j] #) return 0; if (visited[i][j]) return 0; // 2. 标记当前点已访问 visited[i][j] true; // 3. 初始化计数当前点自己算1块 int count 1; // 4. 向四个方向递归搜索 for (int d 0; d 4; d) { int ni i dirs[d][0]; int nj j dirs[d][1]; count dfs(ni, nj); } // 5. 返回总数 return count; }这段代码清晰体现了DFS“探索-回溯”的过程。visited数组确保了每个格子只被计算一次。dirs方向数组的使用让代码简洁且易于扩展到八方向等问题。3.3 主函数逻辑整合与输出在主函数中我们需要初始化visited数组然后以起点坐标调用dfs函数并输出结果。// 在读取完 grid 和找到起点 start_i, start_j 后 visited.assign(H, vectorbool(W, false)); // 初始化访问数组全部为false int result dfs(start_i, start_j); cout result endl;一个重要的细节visited数组的初始化必须在每个测试案例开始时进行并且大小是H x W。使用vector的assign方法可以方便地重置它。至此一个完整、正确的DFS解法已经完成。它的时间复杂度是O(H * W)因为每个格子最多被访问一次。空间复杂度主要是递归栈和visited数组也是O(H * W)。4. 广度优先搜索BFS解法作为拓展虽然DFS更简洁但理解BFS解法有助于我们掌握另一种重要的搜索范式并为解决最短路径问题打下基础。BFS使用队列FIFO来管理待访问的节点。我们从起点开始将其放入队列并标记已访问。然后只要队列不为空就取出队首节点将其四个方向上未访问且可通行的邻居节点加入队列尾部并标记已访问。在这个过程中我们用一个计数器count来累加访问到的节点数。#include queue #include utility // for pair int bfs(int start_i, int start_j) { int count 0; queuepairint, int q; // 初始化起点入队并标记 if (grid[start_i][start_j] ! #) { // 再次确认起点合法 visited[start_i][start_j] true; q.push({start_i, start_j}); } while (!q.empty()) { auto [i, j] q.front(); // C17 结构化绑定更清晰 q.pop(); count; // 每处理一个节点计数1 // 遍历四个方向 for (int d 0; d 4; d) { int ni i dirs[d][0]; int nj j dirs[d][1]; // 检查新位置是否合法且未访问 if (ni 0 ni H nj 0 nj W grid[ni][nj] . !visited[ni][nj]) { visited[ni][nj] true; q.push({ni, nj}); } } } return count; }BFS与DFS的对比访问顺序DFS是“钻探式”的BFS是“扩散式”的。数据结构DFS隐式使用系统栈BFS显式使用队列。适用场景对于单纯的连通块计数两者皆可。若需要“最短步数”或“最近距离”BFS是首选因为它首次访问到某个节点时经过的步数一定是最少的。代码复杂度BFS的循环结构稍长但避免了递归的潜在栈溢出问题。在实际做题时如果你对递归理解深刻用DFS如果你对循环和队列更熟悉或者题目网格可能非常大用BFS。我建议两者都要会写。5. 代码优化与技巧让程序更健壮高效基础的DFS/BFS代码已经能解决题目但一个优秀的程序员会思考如何让它更好。下面分享几个优化和技巧。5.1 避免使用额外的visited数组visited数组需要额外的O(H*W)空间。我们可以利用原始的grid数组进行“就地标记”。当访问过一个‘.’之后我们将其修改为一个非‘.’和‘#’的字符比如‘*’。这样下次遇到‘*’就知道它已被访问过。修改后的DFS函数核心部分int dfs_inplace(int i, int j) { if (i 0 || i H || j 0 || j W) return 0; if (grid[i][j] ! .) return 0; // 不是‘.’包括‘#’和已访问的‘*’都返回 grid[i][j] *; // 标记为已访问 int count 1; for (int d 0; d 4; d) { count dfs_inplace(i dirs[d][0], j dirs[d][1]); } return count; }优点节省了visited数组的空间。缺点修改了原始输入数据。如果后续还需要使用原始网格数据这种方法就不适用。在算法竞赛中通常一个测试用例处理完就丢弃了所以这个方法很常用。5.2 方向数组的灵活运用我们使用了dirs[4][2]来表示四个方向。这是一种非常优雅和通用的做法。如果题目变成可以走八个方向包括对角线我们只需要将dirs数组扩展为8行即可{{-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1}, {1,0}, {1,1}}。代码的其他部分完全不用改动这体现了良好的可扩展性。5.3 输入处理的鲁棒性题目输入可能包含多余的空格或换行。使用cin string读取一行字符串是相对安全的因为它会跳过开头的空白字符直到读取一个非空白字符开始。但更稳妥的做法是使用getline(cin, str)但要注意在cin W H后缓冲区会留下一个换行符需要用cin.ignore()忽略掉。对于算法题通常数据格式规整cin grid[i]足矣。6. 从“红与黑”延伸掌握网格类DFS/BFS的解题模板“红与黑”的本质是无向图连通分量问题。掌握了它你就掌握了一类问题的通用解法。我们可以抽象出一个解题模板数据表示用二维字符数组或整型数组表示网格。用方向数组dirs定义移动规则。状态标记使用一个与原网格同尺寸的visited数组或通过修改原网格进行就地标记。遍历入口找到所有需要开始搜索的起点可能是单个起点也可能是遍历所有未访问的合法点用于统计多个连通块。搜索函数DFS递归函数。先判断边界与合法性标记然后对每个方向递归调用自身累加结果。BFS队列循环。起点入队标记。循环取队首处理将未访问的合法邻居入队标记。结果收集在搜索过程中或搜索返回后收集需要的答案如连通块大小、数量、是否可达等。这个模板可以解决大量LeetCode、洛谷上的类似题目例如岛屿数量将‘.’视为水‘0’‘#’视为陆地‘1’计算‘1’的连通块数量。被围绕的区域从边界上的‘O’开始DFS/BFS标记所有与之相连的‘O’这些是不被围绕的剩下的‘O’就是被围绕的。腐烂的橘子多源BFS的经典应用从所有腐烂的橘子开始同时进行BFS扩散计算时间。7. 常见错误与调试技巧实录即便思路清晰实现时也难免出错。下面是我在带新人和自己刷题过程中总结的关于这类问题的几个高频“坑点”。7.1 数组越界访问这是递归或循环中最常见的错误。在dfs函数内部一定要先检查坐标(i, j)是否在网格范围内然后再去访问grid[i][j]。顺序反了就会导致运行时错误如segmentation fault。错误示范int dfs_bad(int i, int j) { if (grid[i][j] #) return 0; // 危险可能i,j已经越界 if (i 0 || i H || j 0 || j W) return 0; // 检查放后面了 // ... }正确的做法如前面所示将边界检查放在最前面。7.2 忘记标记已访问状态这是导致无限递归和栈溢出的罪魁祸首。如果进入一个点后不立即标记为已访问那么在递归到邻居节点后邻居节点又可能递归回当前节点形成循环。visited[i][j] true;这行代码必须放在通过合法性检查之后开始递归探索之前。7.3 行、列索引混淆这是一个“低级”但极易犯的错误。记住我们通常用第一个索引表示行号垂直方向i第二个索引表示列号水平方向j。grid[i][j]。在读取数据时外层循环是i从0到H-1内层循环是j从0到W-1。很多题目样例是正方形网格这个错误可能被掩盖一旦遇到长方形网格错误就暴露了。7.4 多测试用例未重置状态题目往往包含多个独立测试用例。处理完一个用例后必须将visited数组、grid数组如果就地修改了以及其他全局状态重置。否则上一个用例的数据会污染下一个用例。使用vector的assign方法或memset对于C风格数组来重置visited数组。如果就地修改了grid则需要重新读入数据或从备份恢复。7.5 递归深度问题虽然本题数据范围小但假如网格非常大比如1000x1000且全部连通递归深度将达到10^6远超一般栈空间通常几MB到几MB会导致栈溢出。这时有几种解决方案改用BFS显式队列空间在堆上。使用迭代加深搜索IDS但不太适合此类问题。手动模拟递归栈将递归函数改为用栈操作的迭代形式但这比较复杂。 对于竞赛通常题目会限制数据范围但了解这个风险是必要的。在面试中面试官可能会追问你如何优化。调试技巧小数据测试自己构造一个2x3的小网格在纸上模拟程序运行一步步跟踪变量i, j, count和visited数组的变化。打印调试在DFS函数的开头打印(i, j)坐标和当前grid[i][j]的值观察递归的路径是否合理。使用IDE调试器设置断点单步执行查看调用栈和变量值这是最强大的调试手段。8. 完整可运行代码示例与测试将以上所有部分整合这里提供一份包含DFS解法的完整、健壮的代码并附上测试样例。#include iostream #include vector #include string using namespace std; // 方向数组上下左右 const int dirs[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; int H, W; vectorstring grid; vectorvectorbool visited; // DFS递归函数 int dfs(int i, int j) { // 1. 边界与合法性检查 if (i 0 || i H || j 0 || j W) return 0; if (grid[i][j] #) return 0; if (visited[i][j]) return 0; // 2. 标记访问 visited[i][j] true; // 3. 计数并探索 int count 1; // 当前点 for (int d 0; d 4; d) { int ni i dirs[d][0]; int nj j dirs[d][1]; count dfs(ni, nj); } return count; } int main() { while (cin W H (W || H)) { // 读取网格 grid.resize(H); int start_i -1, start_j -1; for (int i 0; i H; i) { cin grid[i]; for (int j 0; j W; j) { if (grid[i][j] ) { start_i i; start_j j; grid[i][j] .; // 将起点视为可通行点 } } } // 初始化访问数组 visited.assign(H, vectorbool(W, false)); // 执行搜索并输出结果 int result dfs(start_i, start_j); cout result endl; } return 0; }测试样例输入6 9 ....#. .....# ...... ...... ...... ...... ...... #...# .#..#. 0 0输出45解释这是一个9行6列的网格从出发可以到达除了#以外的所有‘.’共计45个。9. 举一反三相关变种题目与思路点拨掌握了“红与黑”的基本解法我们可以挑战一些变种提升解决问题的能力。变种1统计连通块数量岛屿数量问题问题网格中‘1’代表陆地‘0’代表水计算岛屿的数量相连的陆地算一个岛屿。 思路遍历整个网格当遇到一个未被访问的‘1’时以其为起点进行一次DFS或BFS将整个连通块标记为已访问。然后岛屿计数加1。继续遍历寻找下一个未被访问的‘1’。变种2带权值的连通块最大和问题网格中每个格子有一个数值正或负‘#’表示障碍。求从起点出发能到达的连通块中所有数值之和的最大值。 思路在基本的DFS/BFS过程中不再简单计数而是累加访问到的格子的权值。在遍历所有可能的连通块可能需要从每个非障碍且未访问的点出发后维护一个最大值。变种3判断是否存在路径迷宫问题问题给定起点和终点问是否存在一条路径。 思路使用DFS或BFS从起点开始搜索如果能访问到终点则存在路径。BFS在此问题上有一个额外优势如果找到路径那一定是最短路径步数最少。变种4洪水填充Flood Fill问题这就是“红与黑”的图形学版本。给定一个像素点和一个新颜色将与起始点颜色相同且相连的所有像素点染成新颜色。 思路算法一模一样只是将判断条件从grid[i][j] ‘.’改为grid[i][j] oldColor。解决这些变种的关键在于牢牢抓住DFS/BFS遍历连通块这个核心模型然后根据具体问题调整“处理当前节点时做什么”计数、累加、判断、染色以及“需要维护哪些全局状态”。10. 工程实践中的考量与性能优化虽然算法竞赛中的题目对性能要求有明确边界但在实际工程项目中处理类似的大规模网格数据时我们需要考虑更多。1. 内存布局优化对于非常大的静态网格使用vectorvectorbool可能会带来一些内存开销和缓存不友好的问题。可以考虑使用一维数组vectorbool或bitset来模拟二维访问或者使用int数组的位操作来压缩存储访问状态。vectorbool在C中有特化可能不是连续存储需注意。对于纯粹的性能敏感场景C风格的二维数组如bool visited[MAX_H][MAX_W]在栈空间允许的情况下可能具有更好的局部性。2. 迭代DFS栈模拟为了避免递归栈溢出的风险我们可以用显式的栈stack来模拟递归过程。这对于极深搜索或嵌入式环境栈空间小很有用。int dfs_iterative(int start_i, int start_j) { stackpairint, int stk; stk.push({start_i, start_j}); visited[start_i][start_j] true; int count 0; while (!stk.empty()) { auto [i, j] stk.top(); stk.pop(); count; for (int d 0; d 4; d) { int ni i dirs[d][0]; int nj j dirs[d][1]; if (ni 0 ni H nj 0 nj W grid[ni][nj] . !visited[ni][nj]) { visited[ni][nj] true; stk.push({ni, nj}); } } } return count; }注意栈模拟的访问顺序和递归DFS可能不完全相同取决于邻居入栈的顺序但对于连通块计数结果是相同的。3. 并行化思考对于超大规模网格可以考虑将网格分块在不同的线程或进程中对不同的块进行连通性分析然后再合并边界信息。这是一个高级话题涉及并行算法设计。4. 使用并查集Union-Find对于某些连通性问题特别是动态连接查询比如不断添加边并实时查询两点是否连通的场景并查集是比DFS/BFS更高效的数据结构。但对于“红与黑”这种一次性静态网格的全量查询DFS/BFS通常更简单直接。最后我想强调的是学习算法和数据结构不能停留在AC一道题。要像解构“红与黑”这样去理解它背后的模型、掌握它的变种、思考它的优化和工程应用。这道题就像一把钥匙帮你打开了图论搜索世界的大门。多练习多总结把这种二维网格DFS/BFS的模板内化成自己的肌肉记忆以后再遇到类似的题目你就能在几分钟内写出正确且高效的代码。
深度优先搜索(DFS)与广度优先搜索(BFS)实战：从“红与黑”题解到二维网格遍历模板
1. 项目概述从“红与黑”到经典算法题的深度解构“红与黑”这个名字乍一听可能让人联想到司汤达的文学名著或是某种艺术风格。但在我们C程序员的世界里尤其是在算法竞赛和面试刷题的语境下它特指一道非常经典的深度优先搜索DFS或广度优先搜索BFS入门题。这道题通常被归类为“Flood Fill”洪水填充算法的基础应用是检验一个程序员是否真正理解递归和搜索思想的绝佳试金石。我从业十多年带过不少新人发现很多朋友在初次接触这类二维网格遍历问题时思路容易混乱代码写得冗长且易错。今天我们就以这道“红与黑”为引子不仅把这道题本身讲透更要把其背后所代表的二维网格搜索问题的通用解题框架、代码优化技巧以及相关的C核心知识串讲一遍。无论你是正在准备蓝桥杯、ACM等算法竞赛的学生还是希望夯实基础的职场新人这篇文章都将为你提供一个清晰、可复现的实战指南。这道题的典型描述是这样的给定一个由字符构成的二维网格其中‘.’代表黑色瓷砖可通行区域‘#’代表红色瓷砖障碍物‘’代表人的起始位置。人只能站在黑色瓷砖上并且可以向上、下、左、右四个方向移动。问题是从起始位置‘’出发最多可以走过多少块黑色瓷砖同一个瓷砖不能重复计算。这本质上就是计算从起点出发在网格中能连通的所有‘.’格子的数量。理解了这一点我们就抓住了问题的核心——图的遍历。2. 核心思路与算法选型为什么是DFS/BFS面对一个二维网格遍历问题我们首先需要确定算法策略。最常见的候选者就是深度优先搜索DFS和广度优先搜索BFS。对于“红与黑”这类连通块计数问题两者在结果上是等价的都能正确计算出连通区域的大小。但在具体实现和思考角度上它们各有侧重。深度优先搜索DFS的核心思想是“一条路走到黑碰壁再回头”。从起点开始选择一个方向前进直到无法继续遇到边界、障碍物或已访问过的格子然后回溯到上一个分岔点尝试其他方向。DFS通常使用递归来实现代码非常简洁直观非常符合人类“探索”的直觉。其空间复杂度主要取决于递归调用栈的深度在最坏情况下比如整个网格都是连通的‘.’栈深度可能达到O(N*M)。对于“红与黑”这种规模的题目通常网格边长在20以内递归栈完全够用。广度优先搜索BFS的核心思想是“层层推进涟漪扩散”。从起点开始将其放入一个队列然后每次从队列中取出一个位置将其所有未访问的相邻可通行位置加入队列。这个过程就像在水面投入一颗石子波纹一圈圈荡开。BFS天然保证了我们是以“从起点开始的最短距离”的顺序来访问每个节点的虽然对于本题来说这个特性不是必需的。BFS通常使用循环和队列如C的queue实现避免了递归可能带来的栈溢出风险对于极端大的网格代码稍显繁琐但结构清晰。如何选择对于“红与黑”这道题我个人更倾向于使用DFS递归解法。原因有三第一代码量小逻辑清晰易于在笔试面试中快速实现第二题目数据范围通常友好无需担心栈溢出第三DFS的递归过程本身就是对“搜索”这一概念最直接的诠释有助于理解回溯思想。当然掌握BFS的写法也同样重要它是解决最短路径等问题的基础。在后续的“常见问题”章节我会给出两种解法的完整代码并进行对比。确定了算法接下来就是设计程序的核心数据结构。我们通常用一个二维的vectorstring或字符数组来存储网格用一个同样大小的二维布尔数组如vectorvectorbool visited来记录每个格子是否已被访问过防止重复计数。方向数组int dirs[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};定义了上下左右四个方向的坐标偏移这是处理网格类问题的标准技巧能让代码避免写四个冗长的if判断。3. 深度优先搜索DFS解法精讲与实现细节让我们聚焦于最常用的DFS递归解法并一步步拆解其中的每一个细节。3.1 数据读取与初始化任何算法的第一步都是正确地读入数据。“红与黑”题目的输入格式虽然可能有微调但大体类似首先输入两个整数W和H分别代表网格的宽度列数和高度行数。当W和H都为0时输入终止。随后输入H行字符串每行包含W个字符描述整个网格。这里有一个初学者极易踩坑的地方行与列的顺序。我们通常习惯用(行索引 列索引)即(i, j)来定位一个格子其中i的范围是[0, H-1]j的范围是[0, W-1]。在读取时外层循环对应行i内层对应列j。同时在遍历寻找起始点‘’时也要注意这个顺序。#include iostream #include vector using namespace std; int main() { int W, H; while (cin W H (W || H)) { // 循环处理多个案例 vectorstring grid(H); int start_i -1, start_j -1; for (int i 0; i H; i) { cin grid[i]; // 读入一行 // 在读入的同时寻找起点避免二次遍历 for (int j 0; j W; j) { if (grid[i][j] ) { start_i i; start_j j; // 将起点也视为可通行的黑色瓷砖通常题目允许 grid[i][j] .; } } } // ... 后续处理 } return 0; }注意有些题目描述中起点‘’本身也算作一块可通行的瓷砖需要在计数时包含。所以我们在找到起点后可以将其字符临时改为‘.’方便统一处理。当然也可以在DFS函数中单独为‘’位置做判断。3.2 DFS递归函数的编写这是整个程序的核心。递归函数dfs(i, j)的含义是从位置(i, j)出发统计能到达的黑色瓷砖数量并返回这个值。函数设计要点返回值int表示从当前点出发能访问到的瓷砖总数包含当前点。参数当前坐标(i, j)。终止条件递归基当前点越界、是障碍物‘#’、或者已经被访问过。此时应返回0。标记访问一旦进入一个合法的、未访问的点立即将其标记为已访问。这是防止无限递归的关键。递归探索向四个方向分别进行探索并将子问题的结果累加。累加返回当前点的贡献是1自己这块砖加上所有方向探索结果的总和。// 假设 grid 和 visited 是全局变量或在类中可访问 vectorstring grid; vectorvectorbool visited; int H, W; int dirs[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右 int dfs(int i, int j) { // 1. 边界检查与合法性检查 if (i 0 || i H || j 0 || j W) return 0; if (grid[i][j] #) return 0; if (visited[i][j]) return 0; // 2. 标记当前点已访问 visited[i][j] true; // 3. 初始化计数当前点自己算1块 int count 1; // 4. 向四个方向递归搜索 for (int d 0; d 4; d) { int ni i dirs[d][0]; int nj j dirs[d][1]; count dfs(ni, nj); } // 5. 返回总数 return count; }这段代码清晰体现了DFS“探索-回溯”的过程。visited数组确保了每个格子只被计算一次。dirs方向数组的使用让代码简洁且易于扩展到八方向等问题。3.3 主函数逻辑整合与输出在主函数中我们需要初始化visited数组然后以起点坐标调用dfs函数并输出结果。// 在读取完 grid 和找到起点 start_i, start_j 后 visited.assign(H, vectorbool(W, false)); // 初始化访问数组全部为false int result dfs(start_i, start_j); cout result endl;一个重要的细节visited数组的初始化必须在每个测试案例开始时进行并且大小是H x W。使用vector的assign方法可以方便地重置它。至此一个完整、正确的DFS解法已经完成。它的时间复杂度是O(H * W)因为每个格子最多被访问一次。空间复杂度主要是递归栈和visited数组也是O(H * W)。4. 广度优先搜索BFS解法作为拓展虽然DFS更简洁但理解BFS解法有助于我们掌握另一种重要的搜索范式并为解决最短路径问题打下基础。BFS使用队列FIFO来管理待访问的节点。我们从起点开始将其放入队列并标记已访问。然后只要队列不为空就取出队首节点将其四个方向上未访问且可通行的邻居节点加入队列尾部并标记已访问。在这个过程中我们用一个计数器count来累加访问到的节点数。#include queue #include utility // for pair int bfs(int start_i, int start_j) { int count 0; queuepairint, int q; // 初始化起点入队并标记 if (grid[start_i][start_j] ! #) { // 再次确认起点合法 visited[start_i][start_j] true; q.push({start_i, start_j}); } while (!q.empty()) { auto [i, j] q.front(); // C17 结构化绑定更清晰 q.pop(); count; // 每处理一个节点计数1 // 遍历四个方向 for (int d 0; d 4; d) { int ni i dirs[d][0]; int nj j dirs[d][1]; // 检查新位置是否合法且未访问 if (ni 0 ni H nj 0 nj W grid[ni][nj] . !visited[ni][nj]) { visited[ni][nj] true; q.push({ni, nj}); } } } return count; }BFS与DFS的对比访问顺序DFS是“钻探式”的BFS是“扩散式”的。数据结构DFS隐式使用系统栈BFS显式使用队列。适用场景对于单纯的连通块计数两者皆可。若需要“最短步数”或“最近距离”BFS是首选因为它首次访问到某个节点时经过的步数一定是最少的。代码复杂度BFS的循环结构稍长但避免了递归的潜在栈溢出问题。在实际做题时如果你对递归理解深刻用DFS如果你对循环和队列更熟悉或者题目网格可能非常大用BFS。我建议两者都要会写。5. 代码优化与技巧让程序更健壮高效基础的DFS/BFS代码已经能解决题目但一个优秀的程序员会思考如何让它更好。下面分享几个优化和技巧。5.1 避免使用额外的visited数组visited数组需要额外的O(H*W)空间。我们可以利用原始的grid数组进行“就地标记”。当访问过一个‘.’之后我们将其修改为一个非‘.’和‘#’的字符比如‘*’。这样下次遇到‘*’就知道它已被访问过。修改后的DFS函数核心部分int dfs_inplace(int i, int j) { if (i 0 || i H || j 0 || j W) return 0; if (grid[i][j] ! .) return 0; // 不是‘.’包括‘#’和已访问的‘*’都返回 grid[i][j] *; // 标记为已访问 int count 1; for (int d 0; d 4; d) { count dfs_inplace(i dirs[d][0], j dirs[d][1]); } return count; }优点节省了visited数组的空间。缺点修改了原始输入数据。如果后续还需要使用原始网格数据这种方法就不适用。在算法竞赛中通常一个测试用例处理完就丢弃了所以这个方法很常用。5.2 方向数组的灵活运用我们使用了dirs[4][2]来表示四个方向。这是一种非常优雅和通用的做法。如果题目变成可以走八个方向包括对角线我们只需要将dirs数组扩展为8行即可{{-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1}, {1,0}, {1,1}}。代码的其他部分完全不用改动这体现了良好的可扩展性。5.3 输入处理的鲁棒性题目输入可能包含多余的空格或换行。使用cin string读取一行字符串是相对安全的因为它会跳过开头的空白字符直到读取一个非空白字符开始。但更稳妥的做法是使用getline(cin, str)但要注意在cin W H后缓冲区会留下一个换行符需要用cin.ignore()忽略掉。对于算法题通常数据格式规整cin grid[i]足矣。6. 从“红与黑”延伸掌握网格类DFS/BFS的解题模板“红与黑”的本质是无向图连通分量问题。掌握了它你就掌握了一类问题的通用解法。我们可以抽象出一个解题模板数据表示用二维字符数组或整型数组表示网格。用方向数组dirs定义移动规则。状态标记使用一个与原网格同尺寸的visited数组或通过修改原网格进行就地标记。遍历入口找到所有需要开始搜索的起点可能是单个起点也可能是遍历所有未访问的合法点用于统计多个连通块。搜索函数DFS递归函数。先判断边界与合法性标记然后对每个方向递归调用自身累加结果。BFS队列循环。起点入队标记。循环取队首处理将未访问的合法邻居入队标记。结果收集在搜索过程中或搜索返回后收集需要的答案如连通块大小、数量、是否可达等。这个模板可以解决大量LeetCode、洛谷上的类似题目例如岛屿数量将‘.’视为水‘0’‘#’视为陆地‘1’计算‘1’的连通块数量。被围绕的区域从边界上的‘O’开始DFS/BFS标记所有与之相连的‘O’这些是不被围绕的剩下的‘O’就是被围绕的。腐烂的橘子多源BFS的经典应用从所有腐烂的橘子开始同时进行BFS扩散计算时间。7. 常见错误与调试技巧实录即便思路清晰实现时也难免出错。下面是我在带新人和自己刷题过程中总结的关于这类问题的几个高频“坑点”。7.1 数组越界访问这是递归或循环中最常见的错误。在dfs函数内部一定要先检查坐标(i, j)是否在网格范围内然后再去访问grid[i][j]。顺序反了就会导致运行时错误如segmentation fault。错误示范int dfs_bad(int i, int j) { if (grid[i][j] #) return 0; // 危险可能i,j已经越界 if (i 0 || i H || j 0 || j W) return 0; // 检查放后面了 // ... }正确的做法如前面所示将边界检查放在最前面。7.2 忘记标记已访问状态这是导致无限递归和栈溢出的罪魁祸首。如果进入一个点后不立即标记为已访问那么在递归到邻居节点后邻居节点又可能递归回当前节点形成循环。visited[i][j] true;这行代码必须放在通过合法性检查之后开始递归探索之前。7.3 行、列索引混淆这是一个“低级”但极易犯的错误。记住我们通常用第一个索引表示行号垂直方向i第二个索引表示列号水平方向j。grid[i][j]。在读取数据时外层循环是i从0到H-1内层循环是j从0到W-1。很多题目样例是正方形网格这个错误可能被掩盖一旦遇到长方形网格错误就暴露了。7.4 多测试用例未重置状态题目往往包含多个独立测试用例。处理完一个用例后必须将visited数组、grid数组如果就地修改了以及其他全局状态重置。否则上一个用例的数据会污染下一个用例。使用vector的assign方法或memset对于C风格数组来重置visited数组。如果就地修改了grid则需要重新读入数据或从备份恢复。7.5 递归深度问题虽然本题数据范围小但假如网格非常大比如1000x1000且全部连通递归深度将达到10^6远超一般栈空间通常几MB到几MB会导致栈溢出。这时有几种解决方案改用BFS显式队列空间在堆上。使用迭代加深搜索IDS但不太适合此类问题。手动模拟递归栈将递归函数改为用栈操作的迭代形式但这比较复杂。 对于竞赛通常题目会限制数据范围但了解这个风险是必要的。在面试中面试官可能会追问你如何优化。调试技巧小数据测试自己构造一个2x3的小网格在纸上模拟程序运行一步步跟踪变量i, j, count和visited数组的变化。打印调试在DFS函数的开头打印(i, j)坐标和当前grid[i][j]的值观察递归的路径是否合理。使用IDE调试器设置断点单步执行查看调用栈和变量值这是最强大的调试手段。8. 完整可运行代码示例与测试将以上所有部分整合这里提供一份包含DFS解法的完整、健壮的代码并附上测试样例。#include iostream #include vector #include string using namespace std; // 方向数组上下左右 const int dirs[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; int H, W; vectorstring grid; vectorvectorbool visited; // DFS递归函数 int dfs(int i, int j) { // 1. 边界与合法性检查 if (i 0 || i H || j 0 || j W) return 0; if (grid[i][j] #) return 0; if (visited[i][j]) return 0; // 2. 标记访问 visited[i][j] true; // 3. 计数并探索 int count 1; // 当前点 for (int d 0; d 4; d) { int ni i dirs[d][0]; int nj j dirs[d][1]; count dfs(ni, nj); } return count; } int main() { while (cin W H (W || H)) { // 读取网格 grid.resize(H); int start_i -1, start_j -1; for (int i 0; i H; i) { cin grid[i]; for (int j 0; j W; j) { if (grid[i][j] ) { start_i i; start_j j; grid[i][j] .; // 将起点视为可通行点 } } } // 初始化访问数组 visited.assign(H, vectorbool(W, false)); // 执行搜索并输出结果 int result dfs(start_i, start_j); cout result endl; } return 0; }测试样例输入6 9 ....#. .....# ...... ...... ...... ...... ...... #...# .#..#. 0 0输出45解释这是一个9行6列的网格从出发可以到达除了#以外的所有‘.’共计45个。9. 举一反三相关变种题目与思路点拨掌握了“红与黑”的基本解法我们可以挑战一些变种提升解决问题的能力。变种1统计连通块数量岛屿数量问题问题网格中‘1’代表陆地‘0’代表水计算岛屿的数量相连的陆地算一个岛屿。 思路遍历整个网格当遇到一个未被访问的‘1’时以其为起点进行一次DFS或BFS将整个连通块标记为已访问。然后岛屿计数加1。继续遍历寻找下一个未被访问的‘1’。变种2带权值的连通块最大和问题网格中每个格子有一个数值正或负‘#’表示障碍。求从起点出发能到达的连通块中所有数值之和的最大值。 思路在基本的DFS/BFS过程中不再简单计数而是累加访问到的格子的权值。在遍历所有可能的连通块可能需要从每个非障碍且未访问的点出发后维护一个最大值。变种3判断是否存在路径迷宫问题问题给定起点和终点问是否存在一条路径。 思路使用DFS或BFS从起点开始搜索如果能访问到终点则存在路径。BFS在此问题上有一个额外优势如果找到路径那一定是最短路径步数最少。变种4洪水填充Flood Fill问题这就是“红与黑”的图形学版本。给定一个像素点和一个新颜色将与起始点颜色相同且相连的所有像素点染成新颜色。 思路算法一模一样只是将判断条件从grid[i][j] ‘.’改为grid[i][j] oldColor。解决这些变种的关键在于牢牢抓住DFS/BFS遍历连通块这个核心模型然后根据具体问题调整“处理当前节点时做什么”计数、累加、判断、染色以及“需要维护哪些全局状态”。10. 工程实践中的考量与性能优化虽然算法竞赛中的题目对性能要求有明确边界但在实际工程项目中处理类似的大规模网格数据时我们需要考虑更多。1. 内存布局优化对于非常大的静态网格使用vectorvectorbool可能会带来一些内存开销和缓存不友好的问题。可以考虑使用一维数组vectorbool或bitset来模拟二维访问或者使用int数组的位操作来压缩存储访问状态。vectorbool在C中有特化可能不是连续存储需注意。对于纯粹的性能敏感场景C风格的二维数组如bool visited[MAX_H][MAX_W]在栈空间允许的情况下可能具有更好的局部性。2. 迭代DFS栈模拟为了避免递归栈溢出的风险我们可以用显式的栈stack来模拟递归过程。这对于极深搜索或嵌入式环境栈空间小很有用。int dfs_iterative(int start_i, int start_j) { stackpairint, int stk; stk.push({start_i, start_j}); visited[start_i][start_j] true; int count 0; while (!stk.empty()) { auto [i, j] stk.top(); stk.pop(); count; for (int d 0; d 4; d) { int ni i dirs[d][0]; int nj j dirs[d][1]; if (ni 0 ni H nj 0 nj W grid[ni][nj] . !visited[ni][nj]) { visited[ni][nj] true; stk.push({ni, nj}); } } } return count; }注意栈模拟的访问顺序和递归DFS可能不完全相同取决于邻居入栈的顺序但对于连通块计数结果是相同的。3. 并行化思考对于超大规模网格可以考虑将网格分块在不同的线程或进程中对不同的块进行连通性分析然后再合并边界信息。这是一个高级话题涉及并行算法设计。4. 使用并查集Union-Find对于某些连通性问题特别是动态连接查询比如不断添加边并实时查询两点是否连通的场景并查集是比DFS/BFS更高效的数据结构。但对于“红与黑”这种一次性静态网格的全量查询DFS/BFS通常更简单直接。最后我想强调的是学习算法和数据结构不能停留在AC一道题。要像解构“红与黑”这样去理解它背后的模型、掌握它的变种、思考它的优化和工程应用。这道题就像一把钥匙帮你打开了图论搜索世界的大门。多练习多总结把这种二维网格DFS/BFS的模板内化成自己的肌肉记忆以后再遇到类似的题目你就能在几分钟内写出正确且高效的代码。