【优选算法】BFS解决FloodFill算法

一、经验总结

什么是FloodFill算法？

FloodFill算法是一种用于填充连通区域的算法，通常用于图像处理和计算机图形学中。它从给定的起始点开始，向周围相邻的像素进行扩散填充，直到遇到边界或者其他指定条件停止。

FloodFill算法还可以用于统计连通块的数量，求各连通块的面积等。

BFS解决FloodFill算法

当使用BFS解决FloodFill算法时，可以从一个起始点开始，逐步向外扩展，一层层地遍历并填充相邻的空白区域。

需要注意的点：

1. 使用队列来辅助实现BFS
2. 创建横纵坐标的变化量数组，可以方便地遍历相邻地四个方向
3. 可以使用两种方法防止重复地入队列访问：1.直接修改原数组 2.创建visited数组标记访问；不管是哪种方法都需要在元素入队列时进行修改，以防止同层元素的重复访问

---

二、相关编程题

2.1 图像渲染

题目链接

733. 图像渲染 - 力扣（LeetCode）

题目描述

算法原理

编写代码

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(color == prev) return image;
        int m = image.size(), n = image[0].size();
        queue<PII> que;
        que.push({sr,sc});
        image[sr][sc] = color;
        while(!que.empty())
        {
            auto [r, c] = que.front();
            que.pop();
            for(int i = 0; i < 4; ++i)
            {
                int x = r+dx[i], y = c+dy[i];
                if(x>=0 && x<m && y>=0 && y<n && image[x][y]==prev)
                {
                    que.push({x, y});
                    image[x][y] = color;
                }
            }
        }
        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

---

2.2 岛屿数量

题目链接

200. 岛屿数量 - 力扣（LeetCode）

题目描述

算法原理

编写代码

class Solution {
    typedef pair<int,int> PII;
    vector<vector<bool>> visited;
    int m, n;
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {1, -1, 0, 0};
public:
    int numIslands(vector<vector<char>>& grid) 
    {
        m = grid.size(), n = grid[0].size();
        visited.resize(m, vector<bool>(n, false));
        int ret = 0;
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(grid[i][j]=='1' && !visited[i][j])
                {
                    ++ret;
                    BFS(grid, i, j);
                }
            }
        }
        return ret;
    }
    void BFS(vector<vector<char>>& grid, int sx, int sy)
    {
        queue<PII> que;
        que.push({sx, sy});
        visited[sx][sy] = true;
        while(!que.empty())
        {
            auto [a, b] = que.front();
            que.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&&grid[x][y]=='1'&&!visited[x][y])
                {
                    que.push({x,y});
                    visited[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

---

2.3 岛屿的最大面积

题目链接

695. 岛屿的最大面积 - 力扣（LeetCode）

题目描述

算法原理

同上，只需要在BFS的过程中顺便统计一下陆地面积即可（同样是在入队列时统计面积，防止重复记录）。

编写代码

class Solution {
    typedef pair<int,int> PII;
    vector<vector<bool>> visited;
    int m, n;
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {1, -1, 0, 0};
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) 
    {
        m = grid.size(), n = grid[0].size();
        visited.resize(m, vector<bool>(n, false));
        int area_max = 0;
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(grid[i][j]==1 && !visited[i][j])
                    area_max = max(area_max, BFS(grid, i, j));
            }
        }
        return area_max;
    }
    int BFS(vector<vector<int>>& grid, int sx, int sy)
    {
        int area = 0;
        queue<PII> que;
        que.push({sx, sy});
        visited[sx][sy] = true;
        ++area;
        while(!que.empty())
        {
            auto [a, b] = que.front();
            que.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&&grid[x][y]==1&&!visited[x][y])
                {
                    que.push({x,y});
                    visited[x][y] = true;
                    ++area;
                }
            }
        }
        return area;
    }
};
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

---

2.4 被围绕的区域

题目链接

130. 被围绕的区域 - 力扣（LeetCode）

题目描述

算法原理

编写代码

class Solution {
    int m, n;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
public:
    void solve(vector<vector<char>>& board) {
        m = board.size(), n = board[0].size();
        //1.先将边界上的'O'连通块修改为'.'
        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);
        }
        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);
        }

        //2.将剩下的'O'改为'X'，边界上的'.'改回'O'
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(board[i][j] == 'O') board[i][j] = 'X';
                if(board[i][j] == '.') board[i][j] = 'O';
            }
        }
    }

    void BFS(vector<vector<char>>& board, int sx, int sy)
    {
        queue<pair<int,int>> que;
        que.push({sx, sy});
        board[sx][sy] = '.';
        while(!que.empty())
        {
            auto [a,b] = que.front();
            que.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&&board[x][y]=='O')
                {
                    que.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
51