✨感谢您阅读本篇文章，文章内容是个人学习笔记的整理，如果哪里有误的话还请您指正噢✨
✨ 个人主页：余辉zmh–CSDN博客
✨ 文章所属专栏：搜索回溯算法篇–CSDN博客

一.什么是floodfill算法

一.定义

1. 概念
   • Floodfill算法，也被称为种子填充算法。它是一种在图像或网格数据结构中，从给定的起始点开始，填充与起始点相连通的区域的算法。
2. 连通性概念
   • 这里的连通性可以根据不同的规则来定义，比如四连通（上下左右四个方向相邻）或者八连通（上下左右以及四个对角方向相邻）。

二.算法原理

1. 基本步骤
   • 首先，选择一个起始点（种子点）。
   • 然后，检查这个点的相邻点是否满足填充条件（例如颜色相同或者在某个数值范围内等）。
   • 如果相邻点满足条件，就将其标记为已填充，并继续检查这个新点的相邻点，重复这个过程，直到没有新的满足条件的相邻点为止。
2. 示例
   • 以图像为例，假设我们有一个黑白图像，白色区域是我们要填充的目标区域。我们选择一个白色的种子点，然后按照四连通或者八连通的规则，将与这个种子点相连通的所有白色点都填充成另外一种颜色（比如红色）。

三.应用领域

1. 图像处理
   • 在图像编辑软件中，用于填充封闭区域。例如，当你在Photoshop中使用油漆桶工具填充一个封闭的图形内部时，背后可能就是Floodfill算法在起作用。
2. 计算机图形学
   • 在绘制图形时，可以用于填充多边形等形状的内部区域。
3. 游戏开发
   • 用于地图生成中的区域填充，比如填充一片草地或者水域等地形区域。

下面通过几道例题来讲解如何使用floodfill算法。

二.例题

1.图像渲染

题目：

算法原理：

本道题是最基础的问题，下面的几道题都是采用本题相同的思路或者说搜索的步骤都是相同，因此第一道我会详细讲解，如下图所示，一定要先理解本道题，才能明白这类问题的解决方法。

代码实现：

vector<int> row = {1, -1, 0, 0};
vector<int> col = {0, 0, 1, -1};
int cur;
void dfs1(vector<vector<int>>& image,int i,int j,int color){
    //刚开始时先修改当前位置的颜色，再四个方向移动
    image[i][j] = color;

    for (int k = 0; k < 4;k++){
        int x = i + row[k], y = j + col[k];
        if(x>=0&&x<image.size()&&y>=0&&y<image[i].size()&&image[x][y]==cur){
            dfs1(image, x, y, color);
        }
    }
}
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color){
    //特殊情况，如果要修改的颜色等于当前的颜色，直接返回
    if(image[sr][sc]==color){
        return image;
    }

    cur = image[sr][sc];

    dfs1(image, sr, sc, color);
    return image;
}

2.岛屿数量

题目：

算法原理：

本道题简单来讲，只要找出原始数组中有多少个连通块，就是多少个岛屿数量，因此和上一道题不同的是，这次不能进行一次的深度搜索，而是需要遍历整个数组，先找到一个连通块的起始位置，然后从当前位置使用深度搜索，把当前位置的所有连通块标记为已走过，这样就不会重复搜索，然后使用多少次深度搜索就是有多少个岛屿。

代码实现：

vector<vector<bool>> check;
vector<int> row = {1, -1, 0, 0};
vector<int> col = {0, 0, 1, -1};
int ret1 = 0;
void dfs2(vector<vector<char>>& grid,int i,int j){
    for (int k = 0;k<4;k++){
        int x = i + row[k], y = j + col[k];
        if (x >= 0 && x < grid.size() && y >= 0 && y < grid[i].size() && grid[x][y] == '1' && check[x][y] == false)
        {
            check[x][y] = true;
            dfs2(grid, x, y);
        }
    }
}
int numIslands(vector<vector<char>> &grid){
    //先初始化二维布尔数组
    check.resize(grid.size());
    for (int i = 0; i < check.size();i++){
        check[i].resize(grid[i].size());
    }

    //遍历原始数组先找到目标岛屿也就是1，然后对当前位置进行深度搜索
    for(int i=0;i<grid.size();i++){
        for (int j = 0; j < grid[i].size();j++){
            if(grid[i][j]=='1'&&check[i][j]==false){
                dfs2(grid, i, j);
                ret1++;
            }
        }
    }

    return ret1;
}

3.岛屿的最大面积

题目：

算法原理：

本题是让找到最大岛屿的面积，因此和上一题思路一样，遍历原始数组找到某个岛屿的起始位置，然后使用深度搜索，不同的是，这次要加上一个全局变量，统计每次使用深度搜索的面积，然后更新最大值，本次深度搜索递归调用全部结束后，再回溯将面积置为0，直到找到下一个岛屿从新计数，更新面积最大值。

代码实现：

int ret2 = 0;
vector<int> row = {1, -1, 0, 0};
vector<int> col = {0, 0, 1, -1};
vector<vector<bool>> check;
//这里设置一个每次深度搜索的面积变量，如果设置成参数由于函数的特性会自动回溯，在每次深度搜索的过程中不能回溯
//要本次深度搜索全部结束后再回溯
int path = 0;
void dfs3(vector<vector<int>>&grid,int i,int j){
    //每次递归调用时，面积加一
    path++;
    ret2 = max(ret2, path);

    for (int k = 0;k<4;k++){
        int x = i + row[k], y = j + col[k];
        if (x >= 0 && x < grid.size() && y >= 0 && y < grid[i].size() && grid[x][y] == 1 && check[x][y] == false)
        {
            check[x][y] = true;
            dfs3(grid, x, y);
        }
    }

}
int maxAreaOfIsland(vector<vector<int>>& grid){
    //先初始化二维布尔数组
    check.resize(grid.size());
    for (int i = 0; i < check.size();i++){
        check[i].resize(grid[i].size());
    }

    //遍历原始数组先找到目标岛屿也就是1，然后对当前位置进行深度搜索
    for(int i=0;i<grid.size();i++){
        for (int j = 0; j < grid[i].size();j++){
            if(grid[i][j]==1&&check[i][j]==false){
                check[i][j] = true;
                dfs3(grid, i, j);
                //回溯
                path = 0;
            }
        }
    }

    return ret2;
}

4.被围绕的区域

题目：

算法原理：

本道题的题意要求是将所有和边界相连的连通块不能修改，修改的是剩余的内部连通块，如果正着来写的话会比较麻烦，因为我们找到一个连通块要先判断是否和边界相连，不相连才能修改，因此，可以使用正难则反的思想，反着来找，遍历原始数组的四个边界找到连通块的起始位置，然后进行深度搜索，先修改成其他值比如'.'，表示这个连通块和边界相连不能修改，然后四个边界全部搜索完后，再遍历整个原始数组，遇到表示剩下的连通块的值就修改，遇到'.'就修改回原来的值。

代码实现：

vector<int> row = {1, -1, 0, 0};
vector<int> col = {0, 0, 1, -1};
vector<vector<bool>> check;
int m = 0;
int n = 0;
void dfs4(vector<vector<char>>& board,int i,int j){
    board[i][j] = '.';

    for (int k = 0; k < 4;k++){
        int x = i + row[k], y = j + col[k];
        if(x>=0&&x<=m&&y>=0&&y<=n&&board[x][y]=='O'){
            dfs4(board, x, y);
        }
    }
}
void solve(vector<vector<char>>& board){
    m = board.size() - 1;
    n = board[0].size() - 1;
    //正难则反
    //先将边界上的‘o'通过深度搜索将连通块修改成'.'表示边界上的不能修改
    for (int j = 0; j <= n;j++){
        if(board[0][j]=='O'){
            dfs4(board, 0, j);
        }
        if(board[m][j]=='O'){
            dfs4(board, m, j);
        }
    }
    for (int i = 0; i <= m; i++){
        if(board[i][0]=='O'){
            dfs4(board, i, 0);
        }
        if(board[i][n]=='O'){
            dfs4(board, i, n);
        }
    }

    //遍历原始数组，遇到'o'表示除边界连通块以外需要修改的，遇到'.'表示边界的连通块，修改回'o'
    for (int i = 0; i <= m;i++){
        for (int j = 0; j <= n;j++){
            if(board[i][j]=='.'){
                board[i][j] = 'O';
            }
            else if(board[i][j]=='O'){
                board[i][j] = 'X';
            }
            else{
                continue;
            }
        }
    }
}

5.太平洋大西洋水流问题

题目：

算法原理：

本题的题意较难理解，如果我们把二维数组比作地面的话,数字表示地面上山峰的高度，上和左两边界比作太平洋，下和右两边界比作大西洋，题中要求找的位置其实就是连通块的峰值位置，因为只有最高处才能满足都能流向两个海洋，本题和上一题一样，如果正着找的话比较麻烦，因此也是反着来找会比较简单。正着找比作水从地面往两个海洋流，只能从大到小流，不能从小到大流，找到可以同时流向太平洋（上和左两个边界）大西洋（下和右两个边界）的位置，而反着来就是水分别从两个海洋往地面流，只能从小到大流，不能从大到小流，遇到从大到小的位置也就是峰值就停止，然后标记所有搜索过的位置，当两个海洋标记的位置相同时，就是连通块的峰值，返回即可。

代码实现：

void dfs5(vector<vector<int>>& heights,int i,int j,vector<vector<bool>>& check){
    check[i][j] = true;

    for (int k = 0; k < 4; k++){
        int x = i + row[k], y = j + col[k];
        //对当前位置深度搜索，将四个方向比当前位置高的标记为true
        if(x>=0&&x<heights.size()&&y>=0&&y<heights[x].size()&&check[x][y]==false&&heights[x][y]>=heights[i][j]){
            dfs5(heights, x, y, check);
        }
    }
}
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights){
    int n=heights.size();
    int m = heights[0].size();
    //正难则反，不直接找二维数组中的峰值位置既可以流向太平洋也可以流向大西洋，而是从两个向数组内部倒着流，找到峰值
    //设置两个二维数组用来标记太平洋和大西洋可以流向的位置
    vector<vector<bool>> pac(n, vector<bool>(m));
    vector<vector<bool>> alt(n, vector<bool>(m));

    //先处理太平洋，上左两个边界
    for (int j = 0; j < m; j++){
        dfs5(heights, 0, j, pac);
    }
    for (int i = 0; i < n; i++){
        dfs5(heights, i, 0, pac);
    }

    //再处理大西洋，下右两个边界
    for (int j = 0; j < m; j++){
        dfs5(heights, n - 1, j, alt);
    }
    for (int i = 0; i < n; i++){
        dfs5(heights, i, m - 1, alt);
    }

    //遍历两个二维布尔数组，找到同时为true的位置，返回
    vector<vector<int>> ret;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            if(pac[i][j]==true&&alt[i][j]==true){
                ret.push_back({i,j});
            }
        }
    }

    return ret;
}

6.扫雷游戏

题目：

算法原理：

本道题和上面几道题不同的是不再是上下左右四个方向搜索，而是加上斜方向总共八个方向，只需要在两个移动数组中加上对应的值即可。然后再看本道题，炸弹位置用'M'表示，数字位置表示当前位置的八个相邻位置的炸弹数量，已遍历但是八个相邻位置没有炸弹的用'B'表示，未遍历的空白位置用'E'表示，点中炸弹用'X'表示。

题意要求给定一个起始位置，然后展开周边的位置，遇到周边没有炸弹的空白位置就继续展开，当遇到当前位置的周边存在炸弹时，更改当前位置为周边的炸弹数量，然后停止展开；如果一开始的起始位置就是炸弹位置，直接修改为'X'返回即可。

解决方式，就是先判断其实位置是否是炸弹位置，如果是修改然后返回，如果不是就对当前位置进行深度搜索。深度搜索的实现：先将传过来的位置遍历周边八个方向，统计炸弹数量，然后判断，如果炸弹数量不为零，说明当前位置周边存在炸弹，修改为炸弹数量然后返回停止继续搜索；如果炸弹数量不为零，那就直接更改当前位置为空格也就是'B'，继续依次递归搜索八个方向，递归搜索下一个位置的时候也要先进行判断看下一个搜索的位置是否是未遍历的位置也就是'E'。直到搜索完所有可以到达的位置。

代码实现：

vector<int> dx = {1, -1, 0, 0, -1, -1, 1, 1};
vector<int> dy = {0, 0, 1, -1, 1, -1, 1, -1};
void dfs6(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<board.size()&&y>=0&&y<board[x].size()&&board[x][y]=='M'){
            count++;
        }
    }

    //如果地雷个数不为零，修改当前位置的标记为地雷个数然后返回
    if(count){
        board[i][j] = count + '0';
        return;
    }
    //如果地雷个数为零，先修改当前位置为空格，再分别递归八个方向
    else{
        board[i][j] = 'B';
        for (int k = 0; k < 8; k++){
            int x = i + dx[k], y = j + dy[k];
            //如果相邻方向是为遍历，就递归
            if(x>=0&&x<board.size()&&y>=0&&y<board[x].size()&&board[x][y]=='E'){
                dfs6(board, x, y);
            }
        }
    }
}
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click){
    //如果刚开始就是地雷，直接修改并返回
    if(board[click[0]][click[1]]=='M'){
        board[click[0]][click[1]] = 'X';
        return board;
    }

    dfs6(board, click[0], click[1]);

    return board;
}

7.衣橱整理

题目：

算法原理：

因为力扣上的这道题是根据其他上面的原题改编过来的，具体题意描述的不是很清楚，我自己写的时候就是因为没有搞懂题意，踩了很多坑，题中要求的是只能移动两个方向，但实际答案是要移动四个方向，还有就是各数位之和等等，所以这里借用一下评论区某位大佬的详细题意翻译：

看懂题意后这道题就会变得非常简单，直接从起始位置（0，0）进行依次深度搜索即可，每经过一个位置，判断当前位置的两个下标的数位之和是否小于等于限定值，满足就统计个数，不满足就停止对当前位置的搜索，回到上一个位置，继续搜索，最后返回满足的个数即可。

注意点就是，需要借助一个布尔数组标记已经走过的位置，避免重复计数。

代码实现：

vector<int> dx = {1, -1, 0, 0};
vector<int> dy = {0, 0, 1, -1};

vector<vector<bool>> check;
int ans = 0;
void dfs7(int m,int n,int cnt,int i,int j){
    //现将当前位置标记已走过,个数加一
    ans++;
    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){
            //判断位数之和
            int sum = 0;
            while(x){
                sum +=x % 10;
                x /= 10;
            }
            while(y){
                sum += y % 10;
                y /= 10;
            }
            //上面的两个循环修改了x,y的值，这里要从新赋值
            x = i + dx[k], y = j + dy[k];
            if(sum<=cnt){
                dfs7(m, n, cnt, x, y);
            }
        }
    }
}
int wardrobeFinishing(int m, int n, int cnt){
    //如果cnt为0，直接返回
    if(cnt==0){
        return 1;
    }
    //初始化二维布尔数组
    check.resize(m);
    for (int i = 0; i < m; i++){
        check[i].resize(n);
    }
    //深度搜索
    dfs7(m, n, cnt, 0, 0);
    return ans;
}

以上就是关于floodfill算法例题的讲解，如果哪里有错的话，可以在评论区指正，也欢迎大家一起讨论学习，如果对你的学习有帮助的话，点点赞关注支持一下吧！！！