floodfill算法（DFS办理）

目录
什么是floodfill算法
标题一——733. 图像渲染 - 力扣（LeetCode）
标题二——200. 岛屿数量 - 力扣（LeetCode） 
标题三——695. 岛屿的最大面积 - 力扣（LeetCode） 
标题四—— 130. 被围绕的地区 - 力扣（LeetCode）
标题五——417. 平静洋大西洋水流标题 - 力扣（LeetCode）
标题六——529. 扫雷游戏 - 力扣（LeetCode） 
标题七——LCR 130. 衣橱整理 - 力扣（LeetCode）

---

什么是floodfill算法

啥是 FloodFill 算法呢，最直接的一个应用就是「颜色填充」，就是 Windows 绘画本中谁人小油漆桶的标志，可以把一块被圈起来的地区全部染色。

这种算法思想还在许多其他地方有应用。好比说扫雷游戏，偶然候你点一个方格，会一下子睁开一片地区，这个睁开过程，就是 FloodFill 算法实现的。

类似的，像消消乐这类游戏，相同方块积累到肯定数量，就全部消除，也是 FloodFill 算法的功劳。

通过以上的几个例子，你应该对 FloodFill 算法有个概念了，现在我们要抽象标题，提取共同点。
实现这个FloodFill算法，实在有两种实现方式

• DFS
  
• BFS
  

我们这篇文章只讲解DFS内里的
标题一——733. 图像渲染 - 力扣（LeetCode）

 

这个标题很容易懂吧！！实在我们只需要从标题给的谁人起始位置开始调用dfs。每遍历一个，我们就将它的颜色改成

1. class Solution {
2. public:
3.     // 定义四个方向的移动向量，用于上下左右四个方向的遍历
4.     int dx[4]={0,0,-1,1}; // x方向上的移动：-1（左），1（右），0（不变）
5.     int dy[4]={1,-1,0,0}; // y方向上的移动：1（上），-1（下），0（不变）
7.     // 深度优先搜索函数，用于将指定起始点的相连区域的颜色更改为目标颜色
8.     void dfs(vector<vector<int>>& image, int i, int j, int origincolor, int tar_color)
9.     {
10.         // 将当前点的颜色更改为目标颜色
11.         image[i][j] = tar_color;
12.         
13.         // 遍历四个方向
14.         for(int k=0; k<4; k++)
15.         {
16.             int x = i + dx[k], y = j + dy[k]; // 计算相邻点的坐标
17.             
18.             // 检查相邻点是否在图像范围内且颜色与起始颜色相同
19.             if(x >= 0 && x < image.size() && y >= 0 && y < image[0].size()
20.                 && image[x][y] == origincolor)
21.             {
22.                 // 如果满足条件，则递归地对相邻点进行深度优先搜索
23.                 dfs(image, x, y, origincolor, tar_color);
24.             }
25.         }
26.     }
27.    
28.     // 图像渲染（洪水填充）的主函数
29.     vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
30.         // 如果起始点的颜色已经等于目标颜色，则无需更改，直接返回原图像
31.         if(image[sr][sc] == color) return image;
32.         
33.         // 调用深度优先搜索函数，从起始点开始，将相连区域的颜色更改为目标颜色
34.         dfs(image, sr, sc, image[sr][sc], color);
35.         
36.         // 返回渲染后的图像
37.         return image;
38.     }
39. };

复制代码

标题二——200. 岛屿数量 - 力扣（LeetCode） 

实在，我们之前做了那么多回溯的标题了，我信赖各人都会做这一道。
我们很快就能写出代码，但是我们要考虑一点：我们怎么判断我们走过了哪些点啊？
有两种方法

• 我们可以修改我们遍历过的点——即将我们遍历过的点设置为'2'
  
• 我们也可以使用一个和原数组等大的bool数组，来记录我们走过的点
  

---

   修改我们遍历过的点

1. class Solution {
2. public:
3.     // 定义四个方向的移动：上、下、左、右
4.     // dx数组表示在x方向上的移动，dy数组表示在y方向上的移动
5.     int dx[4]={0,0,-1,1}; // x方向上的移动：-1（左），1（右），0（上/下时不变）
6.     int dy[4]={1,-1,0,0}; // y方向上的移动：1（上），-1（下），0（左/右时不变）
8.     // 深度优先搜索函数，用于遍历并标记所有相连的'1'为'2'
9.     void dfs(vector<vector<char>>& grid, int i, int j) {
10.         // 将当前位置标记为已访问过（'2'）
11.         grid[i][j] = '2';
12.         
13.         // 遍历四个方向
14.         for (int k = 0; k < 4; k++) {
15.             // 计算新位置的坐标
16.             int x = i + dx[k], y = j + dy[k];
17.             
18.             // 检查新位置是否在网格内且为'1'（未访问过的岛屿部分）
19.             if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size()
20.                     && grid[x][y] == '1') {
21.                 // 如果是，则递归访问该位置
22.                 dfs(grid, x, y);
23.             }
24.         }
25.     }
27.     // 计算岛屿数量的函数
28.     int numIslands(vector<vector<char>>& grid) {
29.         int ret = 0; // 记录岛屿数量
30.         
31.         // 遍历整个网格
32.         for (int n = 0; n < grid.size(); n++) {
33.             for (int i = 0; i < grid[0].size(); i++) {
34.                 // 如果当前位置是'1'（岛屿的起始点）
35.                 if (grid[n][i] == '1') {
36.                     // 调用dfs函数遍历并标记这个岛屿的所有部分
37.                     dfs(grid, n, i);
38.                     // 岛屿数量加一
39.                     ret++;
40.                 }
41.             }
42.         }
43.         
44.         // 返回岛屿的总数量
45.         return ret;
46.     }
47. };

复制代码

   使用bool数组版本 

1. class Solution {
2. public:
3.     // 用于记录网格中每个位置是否已被访问过的二维数组
4.     bool check[301][301]={false}; // 假设网格的大小不会超过300x300
6.     // 定义四个方向的移动：上、下、左、右
7.     // dx数组表示在x方向上的移动，dy数组表示在y方向上的移动
8.     int dx[4] = {0, 0, -1, 1}; // x方向上的移动：-1（左），1（右），0（上/下时不变，但在这里主要用于配合dy进行方向移动）
9.     int dy[4] = {1, -1, 0, 0}; // y方向上的移动：1（上），-1（下），0（左/右时不变，但在这里主要用于配合dx进行方向移动）
11.     // 深度优先搜索函数，用于遍历并标记所有相连的'1'为已访问（虽然实际上并未改变grid中的值，但使用了check数组来记录）
12.     void dfs(vector<vector<char>>& grid, int i, int j) {
13.         // 将当前位置标记为已访问过
14.         check[i][j] = true;
15.         
16.         // 遍历四个方向
17.         for (int k = 0; k < 4; k++) {
18.             // 计算新位置的坐标
19.             int x = i + dx[k], y = j + dy[k];
20.             
21.             // 检查新位置是否在网格内、是否为'1'且未被访问过
22.             if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size()
23.                     && grid[x][y] == '1' && check[x][y] == false) {
24.                 // 如果是，则递归访问该位置
25.                 dfs(grid, x, y);
26.             }
27.         }
28.     }
30.     // 计算岛屿数量的函数
31.     int numIslands(vector<vector<char>>& grid) {
32.         int ret = 0; // 记录岛屿数量
33.         
34.         // 遍历整个网格
35.         for (int n = 0; n < grid.size(); n++) {
36.             for (int i = 0; i < grid[0].size(); i++) {
37.                 // 如果当前位置是'1'且未被访问过（即是一个新岛屿的起点）
38.                 if (grid[n][i] == '1' && check[n][i] == false) {
39.                     // 调用dfs函数遍历并标记这个岛屿的所有部分
40.                     dfs(grid, n, i);
41.                     // 岛屿数量加一
42.                     ret++;
43.                 }
44.             }
45.         }
46.         
47.         // 返回岛屿的总数量
48.         return ret;
49.     }
50. };

复制代码

 

标题三——695. 岛屿的最大面积 - 力扣（LeetCode） 

 

 和上题简直一模一样。我们还是考虑一个东西
我们很快就能写出代码，但是我们要考虑一点：我们怎么判断我们走过了哪些点啊？
有两种方法

• 我们可以修改我们遍历过的点——即将我们遍历过的点设置为2
  
• 我们也可以使用一个和原数组等大的bool数组，来记录我们走过的点
  

---

   修改原数组版本

1. class Solution {
2. public:
3.     // 定义四个方向的移动：上、下、左、右
4.     // dx数组表示在x方向上的移动，dy数组表示在y方向上的移动
5.     int dx[4] = {0, 0, -1, 1}; // x方向上的移动：-1（左），1（右），0（上/下时不变，但在这里主要用于配合dy进行方向移动）
6.     int dy[4] = {1, -1, 0, 0}; // y方向上的移动：1（上），-1（下），0（左/右时不变，但在这里主要用于配合dx进行方向移动）
7.     int path;
8.     void dfs(vector<vector<int>>&grid,int i,int j)
9.     {
10.         grid[i][j]=2;
11.         path++;
12.         for(int k=0;k<4;k++)
13.         {
14.             int x = i + dx[k], y = j + dy[k];
15.             if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size()
16.                     && grid[x][y] == 1) {
17.                 dfs(grid,x,y);      
18.                 }
19.         }
20.     }
21.     int maxAreaOfIsland(vector<vector<int>>& grid) {
22.         int ret=0;
23.         for(int n=0;n<grid.size();n++)
24.         {
25.             for(int i=0;i<grid[0].size();i++)
26.             {
27.                 if(grid[n][i]==1)
28.                 {
29.                     path=0;
30.                     dfs(grid,n,i);
31.                     ret=max(path,ret);
32.                 }
33.             }
34.         }
35.         return ret;
36.     }
37. };

复制代码

    使用bool数组版本

1. class Solution {
2. public:
3.     // 定义四个方向的移动：上、下、左、右
4.     // dx数组表示在x方向上的移动，dy数组表示在y方向上的移动
5.     int dx[4] = {0, 0, -1, 1}; // x方向上的移动：-1（左），1（右），0（上/下时不变，但在这里主要用于配合dy进行方向移动）
6.     int dy[4] = {1, -1, 0, 0}; // y方向上的移动：1（上），-1（下），0（左/右时不变，但在这里主要用于配合dx进行方向移动）
7.     int path;
8.     bool check[51][51]={false};
9.     void dfs(vector<vector<int>>&grid,int i,int j)
10.     {
11.         check[i][j]=true;
12.         path++;
13.         for(int k=0;k<4;k++)
14.         {
15.             int x = i + dx[k], y = j + dy[k];
16.             if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size()
17.                     && grid[x][y] == 1&&check[x][y]==false) {
18.                 dfs(grid,x,y);      
19.                 }
20.         }
21.     }
22.     int maxAreaOfIsland(vector<vector<int>>& grid) {
23.         int ret=0;
24.         for(int n=0;n<grid.size();n++)
25.         {
26.             for(int i=0;i<grid[0].size();i++)
27.             {
28.                 if(grid[n][i]==1&&check[n][i]==false)
29.                 {
30.                     check[n][i]=true;
31.                     path=0;
32.                     dfs(grid,n,i);
33.                     ret=max(path,ret);
34.                 }
35.             }
36.         }
37.         return ret;
38.     }
39. };

复制代码

 

标题四—— 130. 被围绕的地区 - 力扣（LeetCode）

 

 这道题相比于之前的floodfill算法题还是有一点难度的。
如果我们直接做是特别贫苦的，所以我们需要转换一下头脑——正难则反
我们不去直接修改内里的'O'，我们先修改外围的‘O'，剩下的'O'就是我们要修改的

• 我们先处理边界的o，遇到一个o就设置成'.'，然后调用dfs探求和它相连的o
  
• 现在数组内里就只剩下'x','.','o'了        
  
• 末了我们将'.'还原成'x'，把'o'修改成'x'
  

我们就很快就能写出下面这个代码

1. class Solution {
2. public:
3.     // 定义四个方向上的行列偏移量，用于DFS遍历
4.     int dx[4] = {1, -1, 0, 0}; // 右、左、下、上
5.     int dy[4] = {0, 0, 1, -1};
7.     // 深度优先搜索函数，用于将与边界上的'O'相连的所有'O'标记为'.'
8.     void dfs(vector<vector<char>>& board, int i, int j) {
9.         board[i][j] = '.'; // 将当前'O'标记为'.'，表示已访问
10.         for (int k = 0; k < 4; k++) { // 遍历四个方向
11.             int x = i + dx[k], y = j + dy[k]; // 计算新坐标
12.             // 检查新坐标是否越界，且新位置的字符是否为'O'
13.             if (x >= 0 && x < board.size() && y >= 0 && y < board[0].size() && board[x][y] == 'O') {
14.                 dfs(board, x, y); // 递归调用，继续DFS
15.             }
16.         }
17.     }
19.     // 主函数，用于执行整个棋盘的处理
20.     void solve(vector<vector<char>>& board) {
21.         int m = board.size(), n = board[0].size(); // 获取棋盘的行数和列数
23.         // 第一步：把边界的'O'相连的联通块，全部修改成'.'
24.         // 遍历棋盘的四个边界，使用DFS将与边界上的'O'相连的所有'O'标记为'.'
25.         for (int j = 0; j < n; j++) { // 遍历第一行和最后一行
26.             if (board[0][j] == 'O') dfs(board, 0, j); // 第一行
27.             if (board[m - 1][j] == 'O') dfs(board, m - 1, j); // 最后一行
28.         }
29.         for (int i = 0; i < m; i++) { // 遍历第一列和最后一列
30.             if (board[i][0] == 'O') dfs(board, i, 0); // 第一列
31.             if (board[i][n - 1] == 'O') dfs(board, i, n - 1); // 最后一列
32.         }
34.         // 第二步：还原
35.         // 将标记为'.'的字符还原为'O'，表示这些'O'与边界相连；将未标记的'O'转换为'X'，表示这些'O'是孤立的
36.         for (int i = 0; i < m; i++)
37.             for (int j = 0; j < n; j++) {
38.                 if (board[i][j] == '.') board[i][j] = 'O'; // 还原与边界相连的'O'
39.                 else if (board[i][j] == 'O') board[i][j] = 'X'; // 将孤立的'O'转换为'X'
40.             }
41.     }
42. };

复制代码

标题五——417. 平静洋大西洋水流标题 - 力扣（LeetCode）

 

 

  看起来好恶心啊，标题都没有看懂啊。
正难则反。
如果直接去判断某⼀个位置是否既能到⼤西洋也能到平静洋，会重复遍历许多路径。

• 我们反着来，从⼤西洋沿岸开始反向 dfs ，这样就能找出那些点可以流向⼤西洋；
  
• 同理，从平静洋沿 岸也反向 dfs ，这样就能找出那些点可以流向平静洋。
  
• 那么，被标志两次的点，就是我们要找的结 果。
  

1. class Solution {
2.     int m, n; // 用于存储矩阵的行数和列数
3.     int dx[4] = {0, 0, 1, -1}; // 定义四个方向的x偏移量，用于上下左右移动
4.     int dy[4] = {1, -1, 0, 0}; // 定义四个方向的y偏移量，用于上下左右移动
6. public:
7.     // 主函数，用于找到可以从太平洋和大西洋到达的陆地单元格
8.     vector<vector<int>> pacificAtlantic(vector<vector<int>>& h) {
9.         m = h.size(), n = h[0].size(); // 初始化行数和列数
10.         vector<vector<bool>> pac(m, vector<bool>(n, false)); // 标记可以从太平洋到达的单元格
11.         vector<vector<bool>> atl(m, vector<bool>(n, false)); // 标记可以从大西洋到达的单元格
12.    
13.         // 1. 先处理太平洋方向，从边界开始深度优先搜索
14.         for (int j = 0; j < n; j++) dfs(h, 0, j, pac); // 从第一行的每个单元格开始搜索
15.         for (int i = 0; i < m; i++) dfs(h, i, 0, pac); // 从第一列的每个单元格开始搜索
16.         
17.         // 2. 处理大西洋方向，从边界开始深度优先搜索
18.         for (int i = 0; i < m; i++) dfs(h, i, n - 1, atl); // 从最后一行的每个单元格开始搜索
19.         for (int j = 0; j < n; j++) dfs(h, m - 1, j, atl); // 从最后一列的每个单元格开始搜索
20.         
21.         vector<vector<int>> ret; // 存储结果，即可以同时从太平洋和大西洋到达的单元格坐标
22.         
23.         // 遍历每个单元格，检查是否同时被pac和atl标记为可达
24.         for (int i = 0; i < m; i++)
25.             for (int j = 0; j < n; j++)
26.                 if (pac[i][j] && atl[i][j])
27.                     ret.push_back({i, j}); // 如果可以同时从两边到达，则加入结果集
28.         return ret; // 返回结果
29.     }
30.    
31.     // 深度优先搜索函数，用于标记可以从给定起点到达的所有单元格
32.     void dfs(vector<vector<int>>& h, int i, int j, vector<vector<bool>>& check) {
33.         check[i][j] = true; // 标记当前单元格为可达
34.         for (int k = 0; k < 4; k++) { // 遍历四个方向
35.             int x = i + dx[k], y = j + dy[k]; // 计算新坐标
36.             // 检查新坐标是否在矩阵范围内，是否未被访问过，且高度不小于当前单元格
37.             if (x >= 0 && x < m && y >= 0 && y < n && check[x][y] == false && h[x][y] >= h[i][j]) {
38.                 dfs(h, x, y, check); // 递归调用，继续搜索
39.             }
40.         }
41.     }
42. };

复制代码

标题六——529. 扫雷游戏 - 力扣（LeetCode） 

 

 

 这个标题就是吓你，但是实在非常简单的

1. class Solution
2. {
3.     int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1}; // 八个方向的x偏移量，用于八个方向的移动（上下左右及四个对角线方向）
4.     int dy[8] = {1, -1, 0, 0, 1, -1, -1, 1}; // 八个方向的y偏移量，用于八个方向的移动（上下左右及四个对角线方向）
5.     int m, n; // 矩阵的行数和列数
7. public:
8.     // 更新地雷板的主函数
9.     vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click)
10.     {
11.         m = board.size(); // 获取行数
12.         n = board[0].size(); // 获取列数
13.         int x = click[0], y = click[1]; // 获取点击位置的坐标
15.         // 如果直接点到地雷
16.         if(board[x][y] == 'M')
17.         {
18.             board[x][y] = 'X'; // 将地雷标记为'X'表示已点击
19.             return board; // 返回更新后的板
20.         }
22.         // 从点击位置开始进行深度优先搜索
23.         dfs(board, x, y);
24.         return board; // 返回更新后的板
25.     }
27.     // 深度优先搜索函数
28.     void dfs(vector<vector<char>>& board, int i, int j)
29.     {
30.         // 统计一下周围的地雷个数
31.         int count = 0;
32.         for(int k = 0; k < 8; k++) // 遍历八个方向
33.         {
34.             int x = i + dx[k], y = j + dy[k]; // 计算新坐标
35.             // 如果新坐标在矩阵范围内且对应位置是地雷
36.             if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M')
37.             {
38.                 count++; // 地雷计数加一
39.             }
40.         }
42.         // 如果周围有地雷
43.         if(count > 0)
44.         {
45.             board[i][j] = count + '0'; // 将当前位置标记为周围地雷的数量（字符形式）
46.             return; // 结束当前搜索
47.         }
48.         else // 如果周围没有地雷
49.         {
50.             board[i][j] = 'B'; // 将当前位置标记为'B'，表示是安全的空地
52.             // 继续搜索周围未探索过的空地（标记为'E'的位置）
53.             for(int k = 0; k < 8; k++)
54.             {
55.                 int x = i + dx[k], y = j + dy[k];
56.                 // 如果新坐标在矩阵范围内且对应位置是未探索过的空地（'E'）
57.                 if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E')
58.                 {
59.                     dfs(board, x, y); // 递归调用，继续搜索
60.                 }
61.             }
62.         }
63.     }
64. };

复制代码

标题七——LCR 130. 衣橱整理 - 力扣（LeetCode）

1. class Solution {
2. public:
3.     int m, n, k; // 矩阵的行数m、列数n和给定的和限制k
4.     bool vis[101][101]; // 访问标记数组，用于记录哪些位置已经被访问过
5.     int ret; // 结果变量，用于记录满足条件的路径数量（或深度优先搜索的访问次数等，具体含义取决于dfs函数的实现）
6.     int dx[4] = {0, 0, -1, 1}; // 四个方向的x偏移量，用于上下左右移动
7.     int dy[4] = {1, -1, 0, 0}; // 四个方向的y偏移量，用于上下左右移动
10.     int wardrobeFinishing(int _m, int _n, int _k) {
11.         m = _m, n = _n, k = _k; // 初始化矩阵大小和和限制
12.         dfs(0, 0); // 从(0, 0)位置开始进行深度优先搜索
13.         return ret; // 返回结果
14.     }
16.     // 深度优先搜索函数
17.     void dfs(int i, int j) {
18.         ret++; // 访问次数加一
19.         vis[i][j] = true; // 标记当前位置为已访问
21.         // 遍历四个方向
22.         for (int k = 0; k < 4; k++) {
23.             int x = i + dx[k], y = j + dy[k]; // 计算新坐标
25.             // 检查新坐标是否在矩阵范围内、是否未被访问过以及是否满足某种条件（通过check函数）
26.             if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && check(x, y))
27.                 dfs(x, y); // 如果满足条件，则递归调用dfs函数继续搜索
28.         }
29.     }
31.     // 坐标(i, j)的数字和是否小于等于k
32.     bool check(int i, int j) {
33.         int tmp = 0;
34.         // 计算坐标i的数字和
35.         while (i) {
36.             tmp += i % 10;
37.             i /= 10;
38.         }
39.         // 计算坐标j的数字和
40.         while (j) {
41.             tmp += j % 10;
42.             j /= 10;
43.         }
44.         // 返回是否满足条件（数字和是否小于等于k）
45.         return tmp <= k;
46.     }
47. };

复制代码

 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。