当前位置：首页 > news >正文

下篇：回溯与剪枝的「智慧寻宝人」——DFS 进阶与网格 / 图论应用

news 2026/7/22 11:21:14

掌握了基础回溯之后，DFS 的真正威力体现在二维网格、图结构、约束满足类问题中。本篇聚焦 DFS 在网格遍历、图连通性、复杂约束回溯中的高阶应用，带你学会「Flood Fill 泛洪算法」和「约束剪枝」两大杀器。

例题 1：岛屿数量

题目：给你一个由'1'（陆地）和'0'（水）组成的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和 / 或竖直方向上相邻的陆地连接形成。

思路讲解这是最经典的 Flood Fill（泛洪填充）问题。遍历网格每一个格子，只要遇到未访问的陆地，就以它为起点启动 DFS，把所有相连的陆地都标记为已访问（直接改成水即可），每启动一次 DFS 就代表发现一座岛屿。

完整代码（C++）

cpp

运行

#include <iostream> #include <vector> using namespace std; class Solution { private: int m, n; // 网格的行数和列数 // 从 (i,j) 出发，把所有相连的陆地淹没（标记为已访问） void dfs(vector<vector<char>>& 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(vector<vector<char>>& 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 向四周探索，逐位匹配单词字符；匹配失败则回溯，注意要标记已访问的位置避免重复使用。

完整代码（C++）

cpp

运行

#include <iostream> #include <vector> #include <string> using namespace std; class Solution { private: int m, n; vector<vector<bool>> visited; // 上下左右四个方向 int dirs[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}}; // index：当前匹配到单词的第几个字符 bool dfs(vector<vector<char>>& 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(vector<vector<char>>& board, string word) { m = board.size(); n = board[0].size(); visited.resize(m, vector<bool>(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 即可。

完整代码（C++）

cpp

运行

#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(vector<vector<char>>& 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(vector<vector<char>>& 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 所有合法数字；填入后递归填下一个格子，若后续无解则回溯换数字。通过行、列、宫格三个数组快速判断数字是否合法，实现强力剪枝。

完整代码（C++）

cpp

运行

#include <iostream> #include <vector> using namespace std; class Solution { private: // 三个标记数组：行、列、3x3 宫格中数字是否已使用 vector<vector<bool>> row; vector<vector<bool>> col; vector<vector<bool>> box; // 找到一个解就返回 true，停止继续搜索 bool dfs(vector<vector<char>>& 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(vector<vector<char>>& board) { // 初始化三个标记数组（下标 0 不用，1-9 对应数字） row.assign(9, vector<bool>(10, false)); col.assign(9, vector<bool>(10, false)); box.assign(9, vector<bool>(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 个格子开始填 } };

代码详解