BFS:FloodFill算法

06-21 1591阅读

文章目录

FloodFill算法简介
1.图像渲染
2.岛屿数量
3.岛屿的最大面积
4.被围绕的区域
总结

FloodFill算法简介

Flood Fill算法是一种用于确定与某个给定节点相连的区域的算法，常用于计算机图形学和图像处理。该算法可以用于诸如填充多边形、检测连通区域等任务。Flood Fill算法有多种实现方式，其中最常见的是递归方法和使用栈或队列的迭代方法。

基本思想
Flood Fill算法从一个初始像素开始，检查该像素的颜色。如果颜色匹配（即需要填充的颜色），则将其填充为新的颜色，然后对相邻的像素重复这一过程，直到所有相连的匹配像素都被填充为止。

FloodFill算法也叫洪水灌溉法，上图中0表示岛屿，1表示海洋，如果要我们求岛屿的个数的话就可以用洪水灌溉法则。

灌溉之后就像上面一样。
接下来，我们来练习几道题熟悉一下FloodFill算法。

1.图像渲染

题目链接
题目：

样例输入和输出:

这道题的意思很简单，就是我们固定一个位置，这个位置的坐标是[sr,sc]这个位置周围的和这个这个区块数字相同数都会被变成新的数字。
以上面这个例子为例，初始坐标是中间坐标，那么渲染的区块就是：
如果利用FloodFill算法的话，我们按顺序灌溉应该是1->2->3->4。

算法原理：
利用BFS的FloodFill算法，这个算法我们只需要借助队列，每次入队列的时候改变当前节点的值。

代码展示：
```
class Solution {
public:
    typedef pair PIL;
    //定义一个方向数组，上下左右四个位置
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    vector floodFill(vector& image, int sr, int sc, int color) 
    {
        //标记一下需要修改的像素值
        int prev=image[sr][sc];
        int m=image.size();
        int n=image[0].size();
        if(prev==color)
        {
            return image;//处理边界情况
        }
        queue q;
        q.push({sr,sc});
        while(q.size())
        {
            auto [a,b]=q.front();
            q.pop();
            image[a][b]=color;
            for(int i=0;i
                int x=a+dx[i];
                int y=b+dy[i];
                if(x=0&&x=0&&y
                    q.push({x,y});
                }
            }
        }
        return image;
    }
};

public:
    typedef pair0,0,1,-1};
    int dy[4]={1,-1,0,0};
    bool vis[301][301];
    int ret=0;
    int m,n;
    void bfs(vector
        queuei,j});
        vis[i][j]=false;
        while(q.size())
        {
            auto [a,b]=q.front();
            q.pop();
            for(int k=0;k
                int x=a+dx[k];
                int y=b+dy[k];
                if(x 
```