floodfill算法

目录

什么是floodfill算法

题目一——733. 图像渲染 - 力扣（LeetCode）

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

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

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

题目五——417. 太平洋大西洋水流问题 - 力扣（LeetCode）

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

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

---

 

什么是floodfill算法

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

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

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

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

实现这个FloodFill算法，其实有两种实现方式

1. DFS
2. BFS

我们这篇文章只讲解DFS里面的

题目一——733. 图像渲染 - 力扣（LeetCode）

 

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

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

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

其实，我们之前做了那么多回溯的题目了，我相信大家都会做这一道。

我们很快就能写出代码，但是我们要考虑一点：我们怎么判断我们走过了哪些点啊？

有两种方法

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

---

修改我们遍历过的点

class Solution {
public:// 定义四个方向的移动：上、下、左、右// dx数组表示在x方向上的移动，dy数组表示在y方向上的移动int dx[4]={0,0,-1,1}; // x方向上的移动：-1（左），1（右），0（上/下时不变）int dy[4]={1,-1,0,0}; // y方向上的移动：1（上），-1（下），0（左/右时不变）// 深度优先搜索函数，用于遍历并标记所有相连的'1'为'2'void dfs(vector<vector<char>>& grid, int i, int j) {// 将当前位置标记为已访问过（'2'）grid[i][j] = '2';// 遍历四个方向for (int k = 0; k < 4; k++) {// 计算新位置的坐标int x = i + dx[k], y = j + dy[k];// 检查新位置是否在网格内且为'1'（未访问过的岛屿部分）if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size()&& grid[x][y] == '1') {// 如果是，则递归访问该位置dfs(grid, x, y);}}}// 计算岛屿数量的函数int numIslands(vector<vector<char>>& grid) {int ret = 0; // 记录岛屿数量// 遍历整个网格for (int n = 0; n < grid.size(); n++) {for (int i = 0; i < grid[0].size(); i++) {// 如果当前位置是'1'（岛屿的起始点）if (grid[n][i] == '1') {// 调用dfs函数遍历并标记这个岛屿的所有部分dfs(grid, n, i);// 岛屿数量加一ret++;}}}// 返回岛屿的总数量return ret;}
};

使用bool数组版本 

class Solution {
public:// 用于记录网格中每个位置是否已被访问过的二维数组bool check[301][301]={false}; // 假设网格的大小不会超过300x300// 定义四个方向的移动：上、下、左、右// dx数组表示在x方向上的移动，dy数组表示在y方向上的移动int dx[4] = {0, 0, -1, 1}; // x方向上的移动：-1（左），1（右），0（上/下时不变，但在这里主要用于配合dy进行方向移动）int dy[4] = {1, -1, 0, 0}; // y方向上的移动：1（上），-1（下），0（左/右时不变，但在这里主要用于配合dx进行方向移动）// 深度优先搜索函数，用于遍历并标记所有相连的'1'为已访问（虽然实际上并未改变grid中的值，但使用了check数组来记录）void dfs(vector<vector<char>>& grid, int i, int j) {// 将当前位置标记为已访问过check[i][j] = true;// 遍历四个方向for (int k = 0; k < 4; k++) {// 计算新位置的坐标int x = i + dx[k], y = j + dy[k];// 检查新位置是否在网格内、是否为'1'且未被访问过if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size()&& grid[x][y] == '1' && check[x][y] == false) {// 如果是，则递归访问该位置dfs(grid, x, y);}}}// 计算岛屿数量的函数int numIslands(vector<vector<char>>& grid) {int ret = 0; // 记录岛屿数量// 遍历整个网格for (int n = 0; n < grid.size(); n++) {for (int i = 0; i < grid[0].size(); i++) {// 如果当前位置是'1'且未被访问过（即是一个新岛屿的起点）if (grid[n][i] == '1' && check[n][i] == false) {// 调用dfs函数遍历并标记这个岛屿的所有部分dfs(grid, n, i);// 岛屿数量加一ret++;}}}// 返回岛屿的总数量return ret;}
};

 

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

 

 和上题简直一模一样。我们还是考虑一个东西

我们很快就能写出代码，但是我们要考虑一点：我们怎么判断我们走过了哪些点啊？

有两种方法

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

---

修改原数组版本

class Solution {
public:// 定义四个方向的移动：上、下、左、右// dx数组表示在x方向上的移动，dy数组表示在y方向上的移动int dx[4] = {0, 0, -1, 1}; // x方向上的移动：-1（左），1（右），0（上/下时不变，但在这里主要用于配合dy进行方向移动）int dy[4] = {1, -1, 0, 0}; // y方向上的移动：1（上），-1（下），0（左/右时不变，但在这里主要用于配合dx进行方向移动）int path;void dfs(vector<vector<int>>&grid,int i,int j){grid[i][j]=2;path++;for(int k=0;k<4;k++){int x = i + dx[k], y = j + dy[k];if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size()&& grid[x][y] == 1) {dfs(grid,x,y);       }}}int maxAreaOfIsland(vector<vector<int>>& grid) {int ret=0;for(int n=0;n<grid.size();n++){for(int i=0;i<grid[0].size();i++){if(grid[n][i]==1){path=0;dfs(grid,n,i);ret=max(path,ret);}}}return ret;}
};

 使用bool数组版本

class Solution {
public:// 定义四个方向的移动：上、下、左、右// dx数组表示在x方向上的移动，dy数组表示在y方向上的移动int dx[4] = {0, 0, -1, 1}; // x方向上的移动：-1（左），1（右），0（上/下时不变，但在这里主要用于配合dy进行方向移动）int dy[4] = {1, -1, 0, 0}; // y方向上的移动：1（上），-1（下），0（左/右时不变，但在这里主要用于配合dx进行方向移动）int path;bool check[51][51]={false};void dfs(vector<vector<int>>&grid,int i,int j){check[i][j]=true;path++;for(int k=0;k<4;k++){int x = i + dx[k], y = j + dy[k];if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size()&& grid[x][y] == 1&&check[x][y]==false) {dfs(grid,x,y);       }}}int maxAreaOfIsland(vector<vector<int>>& grid) {int ret=0;for(int n=0;n<grid.size();n++){for(int i=0;i<grid[0].size();i++){if(grid[n][i]==1&&check[n][i]==false){check[n][i]=true;path=0;dfs(grid,n,i);ret=max(path,ret);}}}return ret;}
};

 

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

 

 

 这道题相比于之前的floodfill算法题还是有一点难度的。

如果我们直接做是特别麻烦的，所以我们需要转换一下思维——正难则反

我们不去直接修改里面的'O'，我们先修改外围的‘O'，剩下的'O'就是我们要修改的

1. 我们先处理边界的o，遇到一个o就设置成'.'，然后调用dfs寻找和它相连的o
2. 现在数组里面就只剩下'x','.','o'了        
3. 最后我们将'.'还原成'x'，把'o'修改成'x'

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

class Solution {
public:// 定义四个方向上的行列偏移量，用于DFS遍历int dx[4] = {1, -1, 0, 0}; // 右、左、下、上int dy[4] = {0, 0, 1, -1};// 深度优先搜索函数，用于将与边界上的'O'相连的所有'O'标记为'.'void dfs(vector<vector<char>>& board, int i, int j) {board[i][j] = '.'; // 将当前'O'标记为'.'，表示已访问for (int k = 0; k < 4; k++) { // 遍历四个方向int x = i + dx[k], y = j + dy[k]; // 计算新坐标// 检查新坐标是否越界，且新位置的字符是否为'O'if (x >= 0 && x < board.size() && y >= 0 && y < board[0].size() && board[x][y] == 'O') {dfs(board, x, y); // 递归调用，继续DFS}}}// 主函数，用于执行整个棋盘的处理void solve(vector<vector<char>>& board) {int m = board.size(), n = board[0].size(); // 获取棋盘的行数和列数// 第一步：把边界的'O'相连的联通块，全部修改成'.'// 遍历棋盘的四个边界，使用DFS将与边界上的'O'相连的所有'O'标记为'.'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); // 最后一行}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); // 最后一列}// 第二步：还原// 将标记为'.'的字符还原为'O'，表示这些'O'与边界相连；将未标记的'O'转换为'X'，表示这些'O'是孤立的for (int i = 0; i < m; i++)for (int j = 0; j < n; j++) {if (board[i][j] == '.') board[i][j] = 'O'; // 还原与边界相连的'O'else if (board[i][j] == 'O') board[i][j] = 'X'; // 将孤立的'O'转换为'X'}}
};

题目五——417. 太平洋大西洋水流问题 - 力扣（LeetCode）

 

 

  看起来好恶心啊，题目都没有看懂啊。

正难则反。

如果直接去判断某⼀个位置是否既能到⼤西洋也能到太平洋，会重复遍历很多路径。

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

 

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

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

 

 

 这个题目就是吓你，但是其实非常简单的

class Solution 
{int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1}; // 八个方向的x偏移量，用于八个方向的移动（上下左右及四个对角线方向）int dy[8] = {1, -1, 0, 0, 1, -1, -1, 1}; // 八个方向的y偏移量，用于八个方向的移动（上下左右及四个对角线方向）int m, n; // 矩阵的行数和列数public:// 更新地雷板的主函数vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {m = board.size(); // 获取行数n = board[0].size(); // 获取列数int x = click[0], y = click[1]; // 获取点击位置的坐标// 如果直接点到地雷if(board[x][y] == 'M') {board[x][y] = 'X'; // 将地雷标记为'X'表示已点击return board; // 返回更新后的板}// 从点击位置开始进行深度优先搜索dfs(board, x, y);return board; // 返回更新后的板}// 深度优先搜索函数void dfs(vector<vector<char>>& board, int i, int j){// 统计一下周围的地雷个数int count = 0;for(int k = 0; k < 8; k++) // 遍历八个方向{int x = i + dx[k], y = j + dy[k]; // 计算新坐标// 如果新坐标在矩阵范围内且对应位置是地雷if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M'){count++; // 地雷计数加一}}// 如果周围有地雷if(count > 0) {board[i][j] = count + '0'; // 将当前位置标记为周围地雷的数量（字符形式）return; // 结束当前搜索}else // 如果周围没有地雷{board[i][j] = 'B'; // 将当前位置标记为'B'，表示是安全的空地// 继续搜索周围未探索过的空地（标记为'E'的位置）for(int k = 0; k < 8; k++){int x = i + dx[k], y = j + dy[k];// 如果新坐标在矩阵范围内且对应位置是未探索过的空地（'E'）if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E'){dfs(board, x, y); // 递归调用，继续搜索}}}}
};

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

 

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