掌握了基础回溯之后DFS 的真正威力体现在二维网格、图结构、约束满足类问题中。本篇聚焦 DFS 在网格遍历、图连通性、复杂约束回溯中的高阶应用带你学会「Flood Fill 泛洪算法」和「约束剪枝」两大杀器。例题 1岛屿数量题目给你一个由1陆地和0水组成的二维网格请你计算网格中岛屿的数量。岛屿总是被水包围并且每座岛屿只能由水平方向和 / 或竖直方向上相邻的陆地连接形成。思路讲解这是最经典的 Flood Fill泛洪填充问题。遍历网格每一个格子只要遇到未访问的陆地就以它为起点启动 DFS把所有相连的陆地都标记为已访问直接改成水即可每启动一次 DFS 就代表发现一座岛屿。完整代码Ccpp运行#include iostream #include vector using namespace std; class Solution { private: int m, n; // 网格的行数和列数 // 从 (i,j) 出发把所有相连的陆地淹没标记为已访问 void dfs(vectorvectorchar grid, int i, int j) { // 越界或当前不是陆地终止递归 if (i 0 || i m || j 0 || j n || grid[i][j] ! 1) { return; } grid[i][j] 0; // 标记为已访问淹没 // 向上下左右四个方向深度优先遍历 dfs(grid, i - 1, j); // 上 dfs(grid, i 1, j); // 下 dfs(grid, i, j - 1); // 左 dfs(grid, i, j 1); // 右 } public: int numIslands(vectorvectorchar grid) { if (grid.empty()) return 0; m grid.size(); n grid[0].size(); int count 0; // 遍历每个格子 for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { count; // 发现新岛屿 dfs(grid, i, j); // 淹没整座岛屿 } } } return count; } };代码详解方向数组思想这里显式写出四个方向也可以用方向数组dirs {{-1,0},{1,0},{0,-1},{0,1}}简化代码。原地修改技巧直接把访问过的陆地改成0省去了额外的 visited 数组空间复杂度降为 O (1)不计递归栈。计数时机每次进入 DFS 前计数因为一次 DFS 对应一整座岛屿。例题 2单词搜索题目给定一个m x n二维字符网格board和一个字符串单词word。如果word存在于网格中返回true否则返回false。单词必须按照字母顺序通过相邻的单元格内的字母构成其中相邻单元格是水平相邻或垂直相邻的单元格。思路讲解这是二维网格上的回溯问题。遍历网格中每个字符作为起点若与单词首字母匹配就启动 DFS 向四周探索逐位匹配单词字符匹配失败则回溯注意要标记已访问的位置避免重复使用。完整代码Ccpp运行#include iostream #include vector #include string using namespace std; class Solution { private: int m, n; vectorvectorbool visited; // 上下左右四个方向 int dirs[4][2] {{-1,0}, {1,0}, {0,-1}, {0,1}}; // index当前匹配到单词的第几个字符 bool dfs(vectorvectorchar board, string word, int i, int j, int index) { // 匹配到单词最后一个字符成功 if (index word.size() - 1) { return board[i][j] word[index]; } // 当前字符匹配才继续深入 if (board[i][j] word[index]) { visited[i][j] true; // 标记已访问 // 遍历四个方向 for (auto dir : dirs) { int ni i dir[0]; int nj j dir[1]; // 坐标合法且未访问过 if (ni 0 ni m nj 0 nj n !visited[ni][nj]) { if (dfs(board, word, ni, nj, index 1)) { return true; // 找到一条路径就直接返回 } } } visited[i][j] false; // 回溯撤销访问标记 } return false; } public: bool exist(vectorvectorchar board, string word) { m board.size(); n board[0].size(); visited.resize(m, vectorbool(n, false)); // 枚举所有起点 for (int i 0; i m; i) { for (int j 0; j n; j) { if (dfs(board, word, i, j, 0)) { return true; } } } return false; } };代码详解提前返回只要找到一条合法路径就立刻返回 true无需遍历所有可能大幅提速。回溯本质四个方向都探索完后必须取消当前格子的访问标记因为它可能属于其他路径。边界处理先判断 index 是否到末尾再判断字符是否匹配逻辑清晰且避免越界。例题 3被围绕的区域题目给你一个m x n的矩阵board找到所有被X围绕的区域并将这些区域里所有的O用X填充。被围绕的区间不会存在于边界上。思路讲解正向找「被包围的 O」比较复杂逆向思维更简单边界上的 O 以及和边界相连的 O 都不会被包围。我们从四条边界的 O 出发做 DFS把所有不被包围的 O 标记成特殊字符如#最后遍历整个矩阵把剩余的 O 改成 X把#还原成 O 即可。完整代码Ccpp运行#include iostream #include vector using namespace std; class Solution { private: int m, n; int dirs[4][2] {{-1,0}, {1,0}, {0,-1}, {0,1}}; void dfs(vectorvectorchar board, int i, int j) { if (i 0 || i m || j 0 || j n) return; if (board[i][j] ! O) return; // 不是 O 或者已经标记过终止 board[i][j] #; // 标记为「与边界连通不被包围」 for (auto dir : dirs) { dfs(board, i dir[0], j dir[1]); } } public: void solve(vectorvectorchar board) { if (board.empty()) return; m board.size(); n board[0].size(); // 1. 遍历左右边界 for (int i 0; i m; i) { if (board[i][0] O) dfs(board, i, 0); if (board[i][n-1] O) dfs(board, i, n-1); } // 2. 遍历上下边界 for (int j 0; j n; j) { if (board[0][j] O) dfs(board, 0, j); if (board[m-1][j] O) dfs(board, m-1, j); } // 3. 二次遍历O 变 X# 变回 O for (int i 0; i m; i) { for (int j 0; j n; j) { if (board[i][j] O) { board[i][j] X; } else if (board[i][j] #) { board[i][j] O; } } } } };代码详解逆向思维从边界入手标记所有「安全的 O」剩下的 O 自然就是被包围的。两次遍历第一次 DFS 标记第二次修改结果逻辑清晰且时间复杂度仍为 O (mn)。边界 DFS 起点只从四条边上的 O 出发避免了遍历整个矩阵启动 DFS。例题 4解数独题目编写一个程序通过填充空格来解决数独问题。数独的解法需遵循数字 1-9 在每一行、每一列、每个 3x3 宫格内都只能出现一次。思路讲解数独是典型的「约束满足型回溯」问题。我们按格子顺序逐个填空每个位置尝试 1-9 所有合法数字填入后递归填下一个格子若后续无解则回溯换数字。通过行、列、宫格三个数组快速判断数字是否合法实现强力剪枝。完整代码Ccpp运行#include iostream #include vector using namespace std; class Solution { private: // 三个标记数组行、列、3x3 宫格中数字是否已使用 vectorvectorbool row; vectorvectorbool col; vectorvectorbool box; // 找到一个解就返回 true停止继续搜索 bool dfs(vectorvectorchar board, int pos) { // 所有 81 个格子都填完了找到解 if (pos 81) return true; int i pos / 9; // 当前行号 int j pos % 9; // 当前列号 int boxIdx (i / 3) * 3 j / 3; // 所在宫格编号 // 如果当前格子已经有数字直接跳下一个 if (board[i][j] ! .) { return dfs(board, pos 1); } // 尝试填入 1-9 for (int num 1; num 9; num) { // 剪枝行、列、宫格中只要有一个出现过就不能填 if (row[i][num] || col[j][num] || box[boxIdx][num]) { continue; } // 填入数字 board[i][j] num 0; row[i][num] true; col[j][num] true; box[boxIdx][num] true; // 递归填下一个格子如果成功直接返回 if (dfs(board, pos 1)) { return true; } // 回溯撤销填入 board[i][j] .; row[i][num] false; col[j][num] false; box[boxIdx][num] false; } return false; // 1-9 都试完都不行返回失败 } public: void solveSudoku(vectorvectorchar board) { // 初始化三个标记数组下标 0 不用1-9 对应数字 row.assign(9, vectorbool(10, false)); col.assign(9, vectorbool(10, false)); box.assign(9, vectorbool(10, false)); // 先统计已有数字 for (int i 0; i 9; i) { for (int j 0; j 9; j) { if (board[i][j] ! .) { int num board[i][j] - 0; int boxIdx (i / 3) * 3 j / 3; row[i][num] true; col[j][num] true; box[boxIdx][num] true; } } } dfs(board, 0); // 从第 0 个格子开始填 } };代码详解位置编码用pos从 0 到 80 代表 81 个格子通过除法和取模换算出行列简化递归参数。三维约束剪枝行、列、宫格三重校验不合法的数字直接跳过大幅减少搜索分支。提前终止找到第一个解就立刻返回因为题目保证只有唯一解无需继续搜索。谢谢