目录
在算法解题中，矩阵连通性问题是高频考点，而深度优先搜索（DFS）是解决这类问题的核心工具之一。它通过“一条路走到底，不通再回头”的思路，能高效遍历矩阵中相邻的元素，进而完成标记、计数或替换等操作。本文将结合 LeetCode 130.被围绕的区域、695.岛屿的最大面积、200.岛屿数量 和 733.图像渲染 四题，拆解DFS在矩阵问题中的通用解题框架，并对比各题的差异点，帮助大家举一反三。
一、DFS通用解题思路
矩阵问题的核心是“相邻元素”的处理（通常指上下左右四个方向，特殊情况会包含对角线），DFS的作用就是从一个起始点出发，遍历所有与起始点连通的元素，并执行特定操作（如标记、修改值）。其通用步骤可归纳为：
1. 边界判断：遍历矩阵时，先检查当前元素是否越界（行号<0或>=矩阵行数，列号<0或>=矩阵列
数），若越界则直接返回，避免程序报错。
2. 条件筛选：判断当前元素是否符合“可遍历”条件（如是否为目标值、是否已被标记），若不符合
则返回，减少无效遍历。
3. 执行操作：对符合条件的当前元素执行操作（如标记为已访问、修改数值），防止后续重复遍
历。
4. 递归遍历：分别向当前元素的上、下、左、右四个方向递归调用DFS，继续遍历连通元素。
这四题均围绕该框架展开，差异仅在于“条件筛选”和“执行操作”的具体内容，接下来我们逐题分析。
二、逐题拆解
1. LeetCode 130.被围绕的区域——“边界连通元素的保护”
题目核心需求
给定一个 m x n 的矩阵，将所有被 'X' 围绕的 'O' 替换为 'X' ，与矩阵边界直接或间接连通的 'O' 需保留。
解题关键
被围绕的 'O' 的本质是“不与边界连通”，因此我们可以先标记出所有与边界连通的 'O' ，再将未被标记的 'O' 替换为 'X' ，最后还原被标记的 'O' 。
DFS实现步骤
1. 边界遍历：先遍历矩阵的四条边界（第一行、最后一行、第一列、最后一列），若遇到 'O' ，则以该元素为起点执行DFS。
2. DFS标记：在DFS中，将与边界连通的 'O' 标记为临时符号（如 '*' ），避免后续被误替换。
3. 矩阵更新：遍历整个矩阵，将剩余的 'O' （未与边界连通，即被围绕的）替换为 'X' ，将 '*' 还原为 'O' 。
关键代码片段
// DFS：标记与边界连通的'O'为'*'
void dfs(int x, int y, vector<vector<char>>& board) {
// 1.边界判断 + 2.条件筛选（非'O'则返回）
if (x < 0 || x >= board.size() || y < 0 || y >= board[0].size() || board[x][y] != 'O') {
return;
}
// 3.执行操作：标记为'*'
board[x][y] = '*';
// 4.递归遍历四个方向
dfs(x + 1, y, board);
dfs(x - 1, y, board);
dfs(x, y + 1, board);
dfs(x, y - 1, board);
}
void solve(vector<vector<char>>& board) {
if (board.empty()) return;
int m = board.size(), n = board[0].size();
// 遍历边界，标记连通的'O'
for (int i = 0; i < n; i++) {
if (board[0][i] == 'O') dfs(0, i, board); // 第一行
if (board[m-1][i] == 'O') dfs(m-1, i, board); // 最后一行
}
for (int i = 0; i < m; i++) {
if (board[i][0] == 'O') dfs(i, 0, board); // 第一列
if (board[i][n-1] == 'O') dfs(i, n-1, board); // 最后一列
}
// 更新矩阵
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O') board[i][j] = 'X'; // 未标记的'O'替换为'X'
if (board[i][j] == '*') board[i][j] = 'O'; // 标记的'*'还原为'O'
}
}
}2. LeetCode 200.岛屿数量——“连通区域的计数”
题目核心需求
给定一个 m x n 的二进制矩阵， '1' 代表陆地， '0' 代表水域，计算矩阵中岛屿的数量（岛屿是由相邻的 '1' 组成的连通区域，相邻指上下左右）。
解题关键
每遇到一个未被访问的 '1' ，就通过DFS遍历其所有连通的 '1' 并标记为已访问，每完成一次这样的DFS，岛屿数量加1。
DFS实现步骤
1. 矩阵遍历：遍历矩阵中的每个元素，若遇到 '1' 且未被标记，则岛屿数量加1，并执行DFS。
2. DFS标记：在DFS中，将当前的 '1' 标记为 '0' （或其他符号），表示已访问，避免重复计数。
3. 递归遍历：向四个方向递归，将连通的 '1' 全部标记为 '0' 。
关键代码片段
void dfs(int x, int y, vector<vector<char>>& grid) {
// 1.边界判断 + 2.条件筛选（非'1'则返回）
if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] != '1') {
return;
}
// 3.执行操作：标记为'0'（已访问）
grid[x][y] = '0';
// 4.递归遍历四个方向
dfs(x + 1, y, grid);
dfs(x - 1, y, grid);
dfs(x, y + 1, grid);
dfs(x, y - 1, grid);
}
int numIslands(vector<vector<char>>& grid) {
if (grid.empty()) return 0;
int 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(i, j, grid); // 标记整个岛屿
}
}
}
return count;
}3. LeetCode 695.岛屿的最大面积——“连通区域的最大尺寸”
题目核心需求
给定一个 m x n 的二进制矩阵， 1 代表陆地， 0 代表水域，计算矩阵中最大岛屿的面积（岛屿面积为连通的 1 的个数）。
解题关键
与“岛屿数量”类似，但DFS需额外统计每个岛屿的面积（即连通的 1 的个数），并实时更新最大值。
DFS实现步骤
1. 矩阵遍历：遍历每个元素，若遇到 1 且未被标记，执行DFS并计算该岛屿的面积。
2. DFS计数：在DFS中，将当前 1 标记为 0 （已访问），并返回“1 + 四个方向连通区域的面积之和”，即当前岛屿的总面积。
3. 更新最大值：每次计算出一个岛屿的面积后，与当前最大值比较，保留较大值。
关键代码片段
int dfs(int x, int y, vector<vector<int>>& grid) {
// 1.边界判断 + 2.条件筛选（非1则返回0，无面积）
if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] != 1) {
return 0;
}
// 3.执行操作：标记为0（已访问）
grid[x][y] = 0;
// 4.递归遍历四个方向，累加面积
return 1 + dfs(x+1, y, grid) + dfs(x-1, y, grid) + dfs(x, y+1, grid) + dfs(x, y-1, grid);
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
if (grid.empty()) return 0;
int m = grid.size(), n = grid[0].size();
int maxArea = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
int area = dfs(i, j, grid); // 计算当前岛屿面积
maxArea = max(maxArea, area); // 更新最大值
}
}
}
return maxArea;
}4. LeetCode 733.图像渲染——“指定区域的颜色替换”
题目核心需求
给定一个 m x n 的图像（由整数表示颜色），以及一个起始坐标 (sr, sc) 和新颜色 newColor ，将起始坐标所在的“连通区域”（颜色与起始坐标原颜色相同，相邻指上下左右）全部替换为新颜色。
解题关键
若起始坐标的原颜色与新颜色相同，直接返回图像（避免无限递归）；否则通过DFS遍历所有连通的原颜色像素，替换为新颜色。
DFS实现步骤
1. 初始判断：记录起始坐标的原颜色 oldColor ，若 oldColor == newColor ，直接返回图像。
2. DFS替换：在DFS中，将当前像素的颜色替换为 newColor ，并向四个方向递归，仅替换颜色为 oldColor 的像素。
关键代码片段
void dfs(int x, int y, int oldColor, int newColor, vector<vector<int>>& image) {
// 1.边界判断 + 2.条件筛选（非oldColor则返回）
if (x < 0 || x >= image.size() || y < 0 || y >= image[0].size() || image[x][y] != oldColor) {
return;
}
// 3.执行操作：替换为新颜色
image[x][y] = newColor;
// 4.递归遍历四个方向
dfs(x+1, y, oldColor, newColor, image);
dfs(x-1, y, oldColor, newColor, image);
dfs(x, y+1, oldColor, newColor, image);
dfs(x, y-1, oldColor, newColor, image);
}
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
int oldColor = image[sr][sc];
if (oldColor == newColor) return image; // 避免无限递归
dfs(sr, sc, oldColor, newColor, image);
return image;
}三、四题对比
| 题目 | 核心操作 | 条件筛选（DFS终止条件） | 特殊处理 |
| 130.被围绕的区域 | 标记边界连通的'O' | 非'O'或越界 | 需还原标记（*→O）、替换未标记（O→X） |
| 200.岛屿数量 | 标记陆地并计数 | 非'1'或越界 | 每启动一次DFS，岛屿数+1 |
| 695.最大岛屿面积 | 标记陆地并计算面积 | 非1或越界 | DFS返回面积，实时更新最大值 |
| 733.图像渲染 | 替换连通区域的颜色 | 非原颜色或越界，原颜色==新颜色直接返回 | 直接替换为新颜色，无需还原 |
四、总结：DFS解决矩阵问题的“万能模板”
通过以上四题的分析，我们可以提炼出一个“矩阵DFS万能模板”，只需根据题目需求修改 条件筛选 和 执行操作 即可：
// 通用DFS函数：x,y为当前坐标，其他参数根据题目需求补充（如矩阵、目标值、新值等）
void dfs(int x, int y, 额外参数) {
// 1. 边界判断
if (x < 0 || x >= 矩阵行数 || y < 0 || y >= 矩阵列数) {
return;
}
// 2. 条件筛选（是否为目标元素、是否已访问等）
if (矩阵[x][y] 不满足条件) {
return;
}
// 3. 执行操作（标记、修改值、计数等）
对矩阵[x][y]执行具体操作;
// 4. 递归遍历四个方向
dfs(x + 1, y, 额外参数);
dfs(x - 1, y, 额外参数);
dfs(x, y + 1, 额外参数);
dfs(x, y - 1, 额外参数);
}
// 主函数：遍历矩阵，触发DFS
void mainFunction(矩阵类型& 矩阵, 其他参数) {
if (矩阵为空) return;
int 矩阵行数 = 矩阵.size(), 矩阵列数 = 矩阵[0].size();
for (int i = 0; i < 矩阵行数; i++) {
for (int j = 0; j < 矩阵列数; j++) {
if (触发DFS的条件) { // 如遇到未访问的目标元素
dfs(i, j, 额外参数);
}
}
}
// 若需后续处理（如还原标记、返回结果），在此处执行
}矩阵连通性问题的本质是“找到并处理符合条件的连通区域”，DFS通过递归高效实现了这一过程。掌握上述模板后，无论题目要求是标记、计数还是替换，都能快速适配，真正做到“一题通，题题通”。