floodfill算法
目录
题目三——695. 岛屿的最大面积 - 力扣（LeetCode）
题目四—— 130. 被围绕的区域 - 力扣（LeetCode）
题目五——417. 太平洋大西洋水流问题 - 力扣（LeetCode）
题目七——LCR 130. 衣橱整理 - 力扣（LeetCode）
什么是floodfill算法
啥是 FloodFill 算法呢，最直接的一个应用就是「颜色填充」，就是 Windows 绘画本中那个小油漆桶的标志，可以把一块被圈起来的区域全部染色。
这种算法思想还在许多其他地方有应用。比如说扫雷游戏，有时候你点一个方格，会一下子展开一片区域，这个展开过程，就是 FloodFill 算法实现的。
类似的，像消消乐这类游戏，相同方块积累到一定数量，就全部消除，也是 FloodFill 算法的功劳。
通过以上的几个例子，你应该对 FloodFill 算法有个概念了，现在我们要抽象问题，提取共同点。
实现这个FloodFill算法，其实有两种实现方式
- DFS
- 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）
其实，我们之前做了那么多回溯的题目了，我相信大家都会做这一道。
我们很快就能写出代码，但是我们要考虑一点：我们怎么判断我们走过了哪些点啊？
有两种方法
- 我们可以修改我们遍历过的点——即将我们遍历过的点设置为'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）
和上题简直一模一样。我们还是考虑一个东西
我们很快就能写出代码，但是我们要考虑一点：我们怎么判断我们走过了哪些点啊？
有两种方法
- 我们可以修改我们遍历过的点——即将我们遍历过的点设置为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'就是我们要修改的
- 我们先处理边界的o，遇到一个o就设置成'.'，然后调用dfs寻找和它相连的o
- 现在数组里面就只剩下'x','.','o'了
- 最后我们将'.'还原成'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）
看起来好恶心啊，题目都没有看懂啊。
正难则反。
如果直接去判断某⼀个位置是否既能到⼤西洋也能到太平洋，会重复遍历很多路径。
- 我们反着来，从⼤西洋沿岸开始反向 dfs ，这样就能找出那些点可以流向⼤西洋；
- 同理，从太平洋沿 岸也反向 dfs ，这样就能找出那些点可以流向太平洋。
- 那么，被标记两次的点，就是我们要找的结 果。
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和给定的和限制k
bool 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)的数字和是否小于等于k
bool 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;
}
};
原文地址：https://blog.csdn.net/2301_80224556/article/details/144365776
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！