【递归、搜索与回溯算法】DFS解决FloodFill算法

题目描述：

思路讲解：
本道题会给我们起始点和目标颜色 ，让我们将二维数组中起始点和与起始点连通并且与起始点颜色相同点的值修改为目标颜色 ，这里使用DFS解决，从指定初始像素出发，递归修改所有与初始像素原始颜色相同的连通像素，实现图像的填充渲染。以下是具体思路：

• 全局变量：
  • oldcolor：初始像素的原始颜色
  • newcolor：目标填充颜色
  • rows, cols：图像的行数和列数
  • dx, dy：方向数组，代表右、左、上、下四个移动方向
• 函数参数：
  • image：原始图像的二维数组
  • row, col：当前正在处理的像素坐标
• 递归逻辑：
  • 进入 dfs 后，首先将当前像素的颜色改为 newcolor
  • 遍历四个方向，计算新坐标，检查其合法性：
    • 处于图像边界内
    • 像素颜色与 oldcolor 相同
  • 对符合条件的相邻像素 调用 dfs 递归
  • 无显式回溯，因像素颜色被改为 newcolor 后，不会再与 oldcolor 匹配，自然避免重复处理，无需恢复状态
• 终止条件：
  • 当某一方向的相邻像素超出边界，或颜色与 oldcolor 不同时，该方向的递归自然终止

编写代码：

class Solution {int dx[4] = {0,0,-1,1};int dy[4] = {1,-1,0,0};int oldcolor , newcolor;int rows , cols;
public:void dfs(vector<vector<int>>& image , int row , int col){image[row][col] = newcolor;for(int i = 0 ; i < 4 ; i++){int x = row + dx[i] , y = col + dy[i];if(0 <= x && x < rows && 0 <= y && y < cols && image[x][y] == oldcolor){dfs(image,x,y);}}}vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {oldcolor = image[sr][sc];newcolor = color;if(oldcolor == newcolor)    return image;rows = image.size() , cols = image[0].size();dfs(image,sr,sc);return image;}
};

题目描述：

思路讲解：
本道题需要我们找出岛屿的数量。我们可以通过遍历网格中的陆地单元格，DFS递归探索其所有连通的陆地并标记访问状态，从而统计独立岛屿的数量。以下是具体思路：

• 全局变量：
  • dx，dy：方向数组，代表右、左、上、下四个移动方向
  • vis：标记陆地单元格是否已被访问
  • rows，cols：记录网格的行数和列数
• 递归逻辑：
  • 进入 dfs 函数后，首先将当前陆地单元格标记为已访问，防止后续重复探索
  • 遍历四个方向，计算相邻单元格的坐标，并检查其合法性：
    • 坐标在网格边界内
    • 该单元格是未访问的陆地
    • 对符合条件的相邻陆地单元格递归调用 dfs，继续探索其连通的所有陆地，直至该岛屿的所有陆地均被标记访问
• 计数逻辑：
  • 两层循环遍历网格中的每个单元格，若发现未访问的陆地，说明找到一个新的独立岛屿：
    • 岛屿计数器 ans 加 1
    • 调用 dfs 函数，递归标记该岛屿的所有连通陆地为已访问
    • 遍历结束后，返回网格中岛屿的总数

编写代码：

class Solution {int dx[4] = {0, 0, -1, 1};int dy[4] = {1, -1, 0, 0};int rows , cols;vector<vector<bool>> vis;
public:void dfs(vector<vector<char>>& grid , int row , int col){vis[row][col] = true;for(int i = 0 ; i < 4 ; i++){int x = row + dx[i] , y = col + dy[i];if(0 <= x && x < rows && 0 <= y && y < cols && grid[x][y] == '1' && vis[x][y] == false){dfs(grid,x,y);}}}int numIslands(vector<vector<char>>& grid) {rows = grid.size() , cols = grid[0].size();vis = vector<vector<bool>>(rows,vector<bool>(cols,false));int ans = 0;for(int i = 0 ; i < rows ; i++){for(int j = 0 ; j < cols ; j++){if(grid[i][j] == '1' && vis[i][j] == false){ans++;dfs(grid,i,j);}}}return ans;}
};

题目描述：

思路讲解：

本道题需要我们找出岛屿的最大面积。我们可以通过遍历网格中的陆地单元格，DFS递归探索每个岛屿的所有连通陆地，计算其面积并记录最大值。以下是具体思路：

• 全局变量：
  • dx，dy：方向数组，代表右、左、上、下四个移动方向
  • vis：标记陆地单元格是否已被访问
  • rows，cols：记录网格的行数和列数
• 递归逻辑：
  • 进入 dfs 后，首先标记当前单元格为已访问
  • 当前陆地本身计数为 1
  • 遍历四个方向，计算相邻单元格，检查其合法性：
    • 坐标在网格边界内
    • 该单元格是未访问的陆地
  • 对符合条件的相邻陆地，递归调用 dfs 并将返回的面积累加到 ret 中
  • 递归结束后，ret 即为当前岛屿的总面积，返回给上一层
• 计算最大面积逻辑：
  • 两层遍历网格中的每个单元格：
    • 若发现未访问的陆地，调用 dfs 计算该岛屿的面积
    • 用当前岛屿面积更新最大面积
    • 遍历结束后，返回网格中最大的岛屿面积

编写代码：

class Solution {int dx[4] = {0,0,-1,1};int dy[4] = {1,-1,0,0};vector<vector<bool>> vis;int rows , cols;
public:int dfs(vector<vector<int>>& grid , int row , int col){vis[row][col] = true;int ret = 1;for(int i = 0 ; i < 4 ; i++){int x = row + dx[i] , y = col + dy[i];if(0 <= x && x < rows && 0 <= y && y < cols && grid[x][y] == 1 && vis[x][y] == false){ret += dfs(grid,x,y);}}return ret;}int maxAreaOfIsland(vector<vector<int>>& grid) {rows = grid.size() , cols = grid[0].size();vis = vector<vector<bool>>(rows,vector<bool> (cols,false));int ans = 0;for(int i = 0 ; i < rows ; i++){for(int j = 0 ; j < cols ; j++){if(grid[i][j] == 1 && vis[i][j] == false){ans = max(ans , dfs(grid,i,j));}}}return ans;}
};

题目描述：

思路讲解：
本道题给我们一个二维数组，想让我们将被 ‘X’ 包围的 'O’区域中的 ‘O’ 全部替换为 ‘X’，但是想直接找到被 ‘X’ 包围的 ‘O’ 并替换为 'X’需要两个步骤，首先是通过一次DFS判断该区域是否被包围，再通过一次DFS将被 ‘X’ 包围的 ‘O’ 替换为 ‘X’。

正向麻烦的话，就可以反向思考。先找出所有不被围绕的 ‘O’（即位于二维数组边缘或与边缘 ‘O’ 相连的 ‘O’），并将这些 ‘O’ 替换处 ‘O’ 和 ‘X’ 以外的字符；然后将剩余的 ‘O’（被围绕的区域）替换为 ‘X’。以下是具体思路：

• 全局变量：
  • dx，dy：方向数组，代表右、左、上、下四个移动方向
  • vis：标记已处理的 “O” 单元格
  • rows，cols：记录网格的行数和列数
• 递归逻辑：
  • 进入 dfs 后，将当前边缘相连的 “O” 单元格标记为 ‘H’
  • 遍历四个方向，计算相邻单元格，检查其合法性：
    • 坐标在网格边界内
    • 该单元格是未访问的 “O”
    • 对符合条件的相邻 “O”，标记为已访问后递归调用 dfs，继续标记其连通的 “O” 为 ‘H’，直至所有与边缘相连的 “O” 均被标记
• 完整思路：
  • 遍历网格的四条边缘（第一行、最后一行、第一列、最后一列），对边缘上的 “O” 启动 DFS，将其及所有连通的 “O” 标记为 ‘H’
  • 遍历整个网格，将剩余未被标记为 ‘H’ 的 “O”替换为 ‘X’
  • 将临时标记为 ‘H’ 的单元格恢复为 ‘O’，最终得到仅保留未被围绕 “O” 的网格

编写代码：

class Solution {int dx[4] = {0, 0, -1, 1};int dy[4] = {1, -1, 0, 0};int rows, cols;
public:void dfs(vector<vector<char>>& board, vector<vector<bool>>& vis, int row, int col) {board[row][col] = 'H';for (int i = 0; i < 4; i++) {int x = row + dx[i], y = col + dy[i];if (x >= 0 && x < rows && y >= 0 && y < cols && board[x][y] == 'O' && vis[x][y] == false) {vis[x][y] = true;dfs(board,vis,x,y);}}}void solve(vector<vector<char>>& board) {rows = board.size(), cols = board[0].size();vector<vector<bool>> vis(rows, vector<bool>(cols, false));for (int i = 0; i < cols; i++) {if (board[0][i] == 'O' && vis[0][i] == false) {dfs(board, vis, 0 , i);}if (board[rows - 1][i] == 'O' && vis[rows - 1][i] == false) {dfs(board, vis, rows - 1, i);}}for (int i = 0; i < rows; i++) {if (board[i][0] == 'O' && vis[i][0] == false) {dfs(board, vis, i, 0);}if (board[i][cols - 1] == 'O' && vis[i][cols - 1] == false) {dfs(board, vis, i, cols - 1);}}for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {if (board[i][j] == 'O')board[i][j] = 'X';else if (board[i][j] == 'H')board[i][j] = 'O';}}}
};

题目描述：

思路讲解：
本道题需要我们找到所有既可流向太平洋又可流向大西洋的单元格。首先想到的思路就是通过递归判断每一个单元格是否满足流向太平洋和大西洋，但是这样会有很多重复路径，导致时间复杂度显著提高。那么我们就转换一下思路，分别标记能流向太平洋和大西洋的单元格，最终取两者的交集得到既可流向太平洋又可流向大西洋的单元格，以下是具体思路：

• 全局变量：
  • dx，dy：方向数组，代表右、左、上、下四个移动方向
  • rows，cols：记录网格的行数和列数
• 递归逻辑：
  • 进入 dfs 后，将当前单元格在对应海洋的标记矩阵中设为 true
  • 遍历四个方向，计算相邻单元格，检查其是否符合 “能流向当前单元格” 的条件
    • 坐标在网格边界内
    • 相邻单元格高度 >= 当前单元格高度
    • 相邻单元格尚未被标记为可流向目标海洋
    • 对符合条件的相邻单元格递归调用 dfs，继续标记其是否能流向目标海洋，直至所有可达单元格均被标记
• 完整流程：
  • 创建 pacific 和 atlantic 两个布尔矩阵，初始均为 false
  • 太平洋：从左边界和上边界的所有单元格启动 DFS，标记所有能流向太平洋的单元格
  • 大西洋：从右边界和下边界的所有单元格启动 DFS，标记所有能流向大西洋的单元格
  • 遍历网格，收集所有在 pacific 和 atlantic 中均被标记为 true 的单元格坐标，即为结果

编写代码：

class Solution {int dx[4] = {0,0,-1,1};int dy[4] = {1,-1,0,0};int rows , cols;
public:void dfs(vector<vector<int>>& heights, vector<vector<bool>>& ocean , int row , int col){ocean[row][col] = true;for(int i = 0 ; i < 4 ; i++){int x = row + dx[i] , y = col + dy[i];if(0 <= x && x < rows && 0 <= y && y < cols && heights[row][col] <= heights[x][y] && ocean[x][y] == false){dfs(heights,ocean,x,y);}}}vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {vector<vector<int>> ans;rows = heights.size() , cols = heights[0].size();vector<vector<bool>>pacific (rows,vector<bool>(cols,false));vector<vector<bool>>atlantic(rows,vector<bool>(cols,false));for(int i = 0 ; i < rows ; i++){dfs(heights,pacific,i,0);dfs(heights,atlantic,i,cols-1);}for(int i = 0 ; i < cols ; i++){dfs(heights,pacific,0,i);dfs(heights,atlantic,rows-1,i);}for(int i = 0 ; i < rows ; i++){for(int j = 0 ; j < cols ; j++){if(pacific[i][j] && atlantic[i][j]){ans.push_back({i,j});}}}return ans;}
};

题目描述：

思路讲解：
本道题需要我们完成扫雷游戏，我们只需要根据点击位置的不同类型执行相应规则即可。以下是具体思路：

• 全局变量：
  • dx，dy：方向数组，代表8 个方向的坐标偏移（上下、左右、4 个对角线）移动方向
  • vis：标记已处理的单元格
  • rows，cols：记录盘面的行数和列数
• 递归逻辑：
  • 进入 dfs 后，首先标记当前单元格为已访问，防止重复处理
  • 遍历 8 个方向，统计当前单元格周围未挖出的地雷（“M”）数量 num
  • 更新当前单元格状态：
    • 若 num > 0，当前单元格修改为对应数字字符，且停止递归
    • 若 num == 0，当前单元格修改为 “B”，继续探索相邻方块
    • 对 8 个方向中未访问的相邻单元格（“E”），递归调用 dfs 进行处理，直至所有可揭露的方块均被处理
• 整体流程：
  • 若点击位置是地雷（“M”），直接将其改为 “X”（已挖出的地雷），游戏结束
  • 若点击位置是空方块（“E”），启动 DFS 递归处理，揭露该方块及所有可探索的相邻方块
  • 完成所有递归处理后，返回修改后的 board

编写代码：

class Solution {int dx[8] = {0,0,-1,1,-1,1,-1,1};int dy[8] = {1,-1,0,0,1,1,-1,-1};int rows , cols;vector<vector<bool>> vis;
public:void dfs(vector<vector<char>>& board, int row , int col){vis[row][col] = true;int num = 0;for(int i = 0 ; i < 8 ; i++){int x = row + dx[i] , y = col + dy[i];if(0 <= x && x < rows && 0 <= y && y < cols && board[x][y] == 'M'){num++;}}if(num == 0){board[row][col] = 'B';}else {board[row][col] = num + '0';return;}for(int i = 0 ; i < 8 ; i++){int x = row + dx[i] , y = col + dy[i];if(0 <= x && x < rows && 0 <= y && y < cols && vis[x][y] == false){dfs(board,x,y);}}}vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {int row = click[0] , col = click[1];rows = board.size() , cols = board[0].size();vis = vector<vector<bool>>(rows,vector<bool>(cols,false));if(board[row][col] == 'M'){board[row][col] = 'X';}else{dfs(board,row,col);}return board;}
};

题目描述：

思路讲解：
本道题需要我们找出需要整理格子的数量，我们可以从衣柜的起始位置 (0,0) 开始，递归探索所有符合整理条件的格子，统计需要整理的格子总数。以下是具体思路：

• 全局变量：
  • dx，dy：方向数组，代表右、左、上、下四个移动方向
  • vis：标记已整理的格子
  • rows，cols：记录网格的行数和列数
  • ans：记录需要整理的格子总数
• 递归逻辑：
  • 进入dfs后，首先将当前格子计入整理总数，并标记为已访问
  • 遍历四个方向，计算相邻格子坐标，检查其是否符合整理条件：
    • 坐标在衣柜边界内
    • 未被整理过
    • 数位和满足条件
  • 对符合条件的相邻格子递归调用dfs，继续探索并计数，直至所有可达的符合条件的格子均被处理

编写代码：

class Solution {int dx[4] = {0,0,-1,1};int dy[4] = {1,-1,0,0};vector<vector<bool>> vis;int rows , cols;int ans = 0;
public:int getsum(int num){int sum = 0;while(num){sum += num % 10;num /= 10;}return sum;}void dfs(int row , int col , int cnt){ans++;vis[row][col] = true;for(int i = 0 ; i < 4 ; i++){int x = row + dx[i] , y = col + dy[i];if( 0 <= x && x < rows && 0 <= y && y < cols && getsum(x) + getsum(y) <= cnt && vis[x][y] == false){dfs(x,y,cnt);}}}int wardrobeFinishing(int m, int n, int cnt) {rows = m , cols = n;vis = vector<vector<bool>>(m,vector<bool>(n,false));dfs(0,0,cnt);return ans;}   
};