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

作者：盐析白兔 | 2024-04-19 08:07:01

踩

洪水灌溉算法

什么是FloodFill算法

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

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

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

图像渲染

题目解析

给一个起始位置，让我们把与起始位置相连（上下左右四个方向）且数字相同的区域全都修改为newcolor

算法原理

BFS：刚开始给定一个位置，一层一层扫描（上下左右方向扩展），值相同就添加进来

第一层扩进来：

接着以新扩进来的为起点，开始上下左右扩展（蓝色为第二、三层扩展）
黄色为第四层扩展

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

代码实现

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’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

算法原理

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

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

代码实现

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

岛屿的最大面积

题目解析

算法原理

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

代码实现

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包围的O

算法原理

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

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

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

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

代码实现

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