当前位置:   article > 正文

算法——BFS解决FloodFill算法_洪水灌溉算法

洪水灌溉算法

什么是FloodFill算法

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

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

BFS——宽度优先遍历:一层一层拨开。还是以最右边为例,从-1开始拓展一层(上下左右)发现能把-2扩展出来,接着继续扩展一层上下左右,-3和-10扩展出来;接着在扩展一层上下左右,把-4和-12扩展出来。image.png

图像渲染

图像渲染

题目解析

给一个起始位置,让我们把与起始位置相连(上下左右四个方向)且数字相同的区域全都修改为newcolorimage.png

算法原理

BFS:刚开始给定一个位置,一层一层扫描(上下左右方向扩展),值相同就添加进来

  1. 第一层扩进来:

image.png

  1. 接着以新扩进来的为起点,开始上下左右扩展(蓝色为第二、三层扩展)image.png

  2. 黄色为第四层扩展

image.png

然后在扩展的过程中,一边扩展一边把值修改为2.为了方便访问上下左右四个方向的数组,可以定义一个dx、dy(x、y的变化量)。原坐标分别去相加就能遍历到四个方向的坐标位置
image.png

代码实现

class Solution 
{
    typedef pair<int, int> PII;
    int dx[4] = {0, 0, 1, -1};   //定义一个变化量dx、dy,(x,y)分别去加就能遍历到上下左右四个方向
    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.empty())
        {
            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;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

岛屿数量

岛屿数量

题目解析

  • 给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。
  • 岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。image.png

算法原理

解法:BFS:
从左往右扫描,当第一次遇到1(陆地)时,就把这块陆地连接的岛屿找到,使用BFS宽搜一遍,找到一个岛屿ret++

这里有一个细节问题,如果第一个1宽搜完之后,到下一个1(蓝色的)如果再上下左右宽搜的话,就会重复统计了,为此我们有两种办法:
1.直接修改原数组为0,但这个方法一般会直接修改接口(我们再笔试刷题时一般都是接口类型的函数)
2.创建一个与原数组同等规模的数组vis[m][n],用来标记已经被BFS过的区域,如果宽搜过记为true,没被宽搜过记为false。此时对下个1进行上下左右宽搜时,如果该区域已经被标记为true就不管即可。每次标记为true时,再让ret++
image.png

代码实现

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;
                }
            }
        }
    }

};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48

岛屿的最大面积

岛屿的最大面积

题目解析

image.png

算法原理

要找到所有连通块中的最大面积,就要先找能统计出一个连通块的面积。先从左到右从上往下扫描矩阵,当遇到一个没有遍历过的1的时候,相当于此时找到一个陆地。我们依旧定义一个bool类型的vis数组,用来标记当前位置是否遍历过。然后我们在BFS过程中不仅要标记,还要搞一个count计算面积。当层序遍历结束后,我们就把count返回给主函数。image.png

代码实现

class Solution 
{
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    bool vis[51][51];
    int m, n;
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(ret, bfs(grid, i, j));
                }
            }
        }
        return ret;
    }

    int bfs(vector<vector<int>>& grid, int i, int j)
    {
        int count = 0;
        queue<pair<int, int>> q;
        q.push({i, j});
        vis[i][j] = true;count++;
        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;
                    count++;
                }
            }
        }
            return count;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48

被围绕的区域

被围绕的区域

题目解析

找到被X包围的Oimage.png

算法原理

扫描区域,当扫描到一个O时,就把与O相连的O一起修改为X。当扫描的边界的O时,要多加一个判断,因为他的下方没有X,此时不属于被包围,故不能修改。

解法一:直接做:先BFS一遍,判断区域是否合法,然后再来一遍开始修改
我们之前的FloodFill算法是一边修改,一边遍历,当到刚刚所说的边界情况时,想再修改回X发现此时周围已经全部变成X了,就无法判断了。

也可能有同学会想到,先遍历一遍,如果发现是好的区域(非边界情况)修改,当是边界情况就不修改,此时需要遍历两次

解法二:正难则反
本题难处理的地方是边界情况的判断。那么我们就可以反过来,先处理边界情况的连通块,先对四条边进行一次遍历,先把边上的连通块都找到,将其修改为无关的字符。接下来只需要遍历(此时不需要再BFS或DFS)矩阵,将矩阵中剩下的的O修改为X,最后再把 . 修改为O即可。因为把边界情况处理过后,此时剩下的O一定都是被包围的。
image.png

代码实现

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] = '.';
                }
            }
        }
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/盐析白兔/article/detail/450721
推荐阅读
相关标签
  

闽ICP备14008679号