当前位置：首页 > article >正文

【算法】BFS系列之 FloodFill 算法

article 2024/9/20 9:23:39

【ps】本篇有 4 道 leetcode OJ。

一、算法简介

二、相关例题

1）图像渲染

.1- 题目解析

.2- 代码编写

2）岛屿数量

.1- 题目解析

.2- 代码编写

3）岛屿的最大面积

.1- 题目解析

.2- 代码编写

4）被围绕的区域

.1- 题目解析

.2- 代码编写

一、算法简介

FloodeFill算法即填充算法，原理就是从一个点开始向四周扩散，向周围可以走到的点填充颜色，直到将可扩散到的点全部填充颜色。

通常使用下面两种方法解决FloodFill算法问题：

BFS （宽搜）算法通常使用队列实现，将起始像素点加入队列中，并不断扩展队列中的像素点，直到队列为空为止。
DFS（深搜）算法通常使用递归实现，在处理当前像素点的相邻像素点时，递归调用 DFS 函数，不断深入直到无法找到相邻像素为止。

假设这一块4*4的方格是一块土地，有凸起的地方，也有凹陷的地方（凹陷的地方用负数表示）。此时下大雨发洪水，会把凹陷的地方填满。绿色圈起来的属于一块区域（上下左右四个方向，有时候题目也会问八个方向包括斜着相连的），题目会问有多少块区域被填满，或者问被填满的最大区域是哪个，或某一块区域的边长是多少。但是本质都是在一块区域找性质相同的连通块。

DFS：深度优先遍历（递归）：从某一点开始一条路走到黑。以最右列的为例，从-1出发，向下->-2->-10->-12，此时发现-12的上下左右都走不了，在拐回去到-10，然后发现-10左边可以走->-4->-3。

BFS：宽度优先遍历：一层一层拨开。还是以最右边为例，从-1开始拓展一层（上下左右）发现能把-2扩展出来，接着继续扩展一层上下左右，-3和-10扩展出来；接着在扩展一层上下左右，把-4和-12扩展出来。

int dx[4] = {0, 0 , -1, 1}; 
int dy[4] = {1, -1 , 0, 0};
// i点加dx，dy就是i点的上下左右的下标

二、相关例题

1）图像渲染

733. 图像渲染

.1- 题目解析

利用 BFS 遍历到与某点相连的所有像素相同的点，然后将其修改成指定的像素即可。

.2- 代码编写

class Solution {
    typedef pair<int, int> PII;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};

public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc,int color) {
        int prev = image[sr][sc];//先标记一下要修改的像素值
        if (prev == color)//处理边界情况
            return image;
        int m = image.size(), n = image[0].size();
        queue<PII> q;
        q.push({sr, sc});
        while (q.size()) {
            auto [a, b] = q.front();
            image[a][b] = color;
            q.pop();
            for (int i = 0; i < 4; i++) { //遍历相邻的四个方向
                int x = a + dx[i], y = b + dy[i];
                if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev) {
                    q.push({x, y});
                }
            }
        }
        return image;
    }
};

2）岛屿数量

200. 岛屿数量

.1- 题目解析

被水（0）围起来的相连的陆地（1）才算一座岛屿。

我们可以遍历整个矩阵，每次找到一块陆地的时候，即找到了一个岛屿，就将其记入最终结果，同时将这个岛屿，全部变成海洋（由1改为0），这样的话，下次遍历到这个岛屿的时候，它已经是海洋了，不会影响最终结果。其中，变成海洋的操作，可以利用 BFS 解决。

但如果在面试中，面试官要求另外不能直接修改原始矩阵，那我们还可以用到一个全局的 bool 类型的矩阵，来记录陆地是否被遍历过。

.2- 代码编写

class Solution {
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    bool vis[301][301];//记录陆地是否被遍历过
    int m, n;

public:
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size(), n = grid[0].size(); //记录矩阵的大小
        int ret = 0;
        for (int i = 0; i < m; i++) { //遍历矩阵，寻找陆地
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1' && !vis[i][j]) {
                    ret++;
                    bfs(grid, i, j); //将这块陆地全都标记一下
                }
            }
        }
        return ret;
    }
    void bfs(vector<vector<char>>& grid, int i, int j) {
        queue<pair<int, int>> q;
        q.push({i, j});
        vis[i][j] = true;
        while (q.size()) {
            auto [a, b] = q.front();
            q.pop();
            for (int k = 0; k < 4; k++) {
                int x = a + dx[k], y = b + dy[k];
                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' &&
                    !vis[x][y]) {
                    q.push({x, y});
                    vis[x][y] = true;
                }
            }
        }
    }
};

3）岛屿的最大面积

695. 岛屿的最大面积

.1- 题目解析

这道题是上一道题的变形。

我们只要在遍历矩阵寻找岛屿的时候，多一步来统计一下当前找出的岛屿面积即可。

.2- 代码编写

class Solution {
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    int m,n;
    bool vis[51][51];
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        m=grid.size(),n=grid[0].size();
        int ret=0;//记录结果
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid[i][j]==1 && !vis[i][j])
                {
                    ret=max(bfs(grid,i,j),ret);
                }
            }
        }
        return ret;
    }
    int bfs(vector<vector<int>>& grid,int i,int j)
    {
        int ret=0;//统计岛屿面积（1的个数）
        queue<pair<int,int>> q;
        q.push({i,j});
        vis[i][j]=true;
        ret++;
        while(q.size())
        {
            auto [a,b]=q.front();q.pop();
            for(int k=0;k<4;k++)
            {
                int x=a+dx[k],y=b+dy[k];
                if(x>=0 && x<m && y>=0 && y<n && grid[x][y]==1 && !vis[x][y])
                {
                    q.push({x,y});
                    vis[x][y]=true;
                    ret++;
                }
            }
            
        }
        return ret;
    }
};

4）被围绕的区域

130. 被围绕的区域

.1- 题目解析

不难想到，可以直接通过 bfs 将所有被 'X' 围起来的 'O' 修改为 'X'，但位于矩阵边缘的 'O' 其实是不必修改的，此时又该如何处理呢？

我们可以选择正难则反，先利用 bfs 将与边缘相连的 'O' 区域修改成无关字符，然后重新遍历矩阵，将没有标记过的 'O' 全修改成 'X' 即可，再把无关字符全还原成'O'。

.2- 代码编写

class Solution {
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    int m,n;
public:
    void solve(vector<vector<char>>& board) {
        m=board.size(),n=board[0].size();
        // 1. 先处理边界上的 'O' 联通块，全部修改成 '.'
        for(int j=0;j<n;j++)
        {
            if(board[0][j]=='O')
                bfs(board,0,j);
            if(board[m-1][j]=='O')
                bfs(board,m-1,j);
        }
        for(int i=0;i<m;i++)
        {
            if(board[i][0]=='O')
                bfs(board,i,0);
            if(board[i][n-1]=='O')
                bfs(board,i,n-1);
        }
        // 2. 还原
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(board[i][j]=='O')
                    board[i][j]='X';
                else if(board[i][j]=='.')
                    board[i][j]='O';
            }
        }
    }
    void bfs(vector<vector<char>>& board,int i,int j)
    {
        queue<pair<int,int>> q;
        q.push({i,j});
        board[i][j]='.';
        while(q.size())
        {
            auto [a,b]=q.front();q.pop();
            for(int k=0;k<4;k++)
            {
                int x=a+dx[k],y=b+dy[k];
                if(x>=0 && x<m && y>=0 && y<n && board[x][y]=='O')
                {
                    q.push({x,y});
                    board[x][y]='.';
                }
            }
        }
    }

};

查看全文

http://www.kler.cn/news/310152.html