FloodFill算法---BFS

码农世界 2024-06-20 后端 89 次浏览 0个评论

一、前言

二、算法模板套路

2.1 创建所需的全局变量：

2.2 BFS模板：

2.3 细节处理：

三、例题练习

3.1 例题1：图像渲染

3.2 例题2：岛屿数量

3.3 例题3：岛屿的最大面积

3.4 例题4：被围绕的区域

一、前言

在这之前我们已经学习了如何使用 DFS 解决 FloodFill 算法，如果有友友对 FloodFill 算法不太熟悉的话可以先看看我之前写的文章：FloodFill算法---DFS。里面详细介绍了什么是FloodFill算法和如何使用DFS来解决。通常 FloodFill 算法使用 DFS 或者 BFS 都可以，DFS 的代码会简洁一些，但是 BFS 可以用来解决最短路问题和拓扑排序。所以本文章可以说是为了后续使用 BFS 解决最短路问题和拓扑排序打下基础。

• 关于BFS的遍历特性：若初始点为左上角，遍历特性如下图所示。

二、算法模板套路

2.1 创建所需的全局变量：

最好设置为静态，因为非静态只有在leetcode上才行，在竞赛中都是要我们自己写Main类的因为main是静态方法所以在方法外面的全局变量要设置为静态的才能被main方法调用。

static boolean[][] vis;//（ 不一定要有）
static int[ ] dx = {0 , 0 , 1 , -1 };
static int[ ] dy = {1 , -1 , 0 , 0 };

• vis这个布尔类型数组来标记我们已经走过的路，防止重复走导致死循环：

还有一种可以不用创建 vis 来标记，直接修改原来数据的值，这个如果是在面试的时候要问一下面试官，原来数组的数值是否可以修改。

• 利用dx，dy 来实现上下左右移动（如果是8个方向的也行）：

for(int k = 0;k < 4;k++){
    int x = i + dx[k];
    int y = j + dy[k];
}

如果是 8 个方向的话可以先画出下图。

在把黄色对应的8个位置写入到dx和dy中。例如：

下面这个例子是从上到下，从左到右写的。

static int[] dx = {-1,-1,-1,0,0,1,1,1};
static int[] dy = {-1,0,1,-1,1,-1,0,1};

2.2 BFS模板：

我们利用 int[ ]来存储坐标。

• 至于要不要回溯，要根据题目要求什么来进行决定。

• x >= 0 && x < n && y >= 0 && y < m 这个可以说是默写了，因为这就是防止越界，每道题目都是这么写的。

public void bfs(char[][] grid, int i, int j) {
        Queue queue = new LinkedList<>();
        queue.add(new int[] { i, j });
        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int a = tmp[0];
            int b = tmp[1];
            vis[a][b] = true;///1
            for (int k = 0; k < 4; k++) {
                int x = a + dx[k];
                int y = b + dy[k];
                if(x >= 0 && x < n && y >= 0 && y < m && !vis[x][y]){
                    queue.add(new int[]{x,y});
                    vis[x][y] = true;///2
                }
            }
        }
    }

2.3 细节处理：

不知道大家有没有注意到在模板那里，我在代码里标记了1和2，现在我要问问友友们，2处的代码能否省略？

答：不能省略。因为如果不加上代码2的话，有些节点会重复进入，导致代码超时（这个要想清楚，因为我当时没有代码2，检查代码检查半天才找到😭😭😭）。友友们在学完下面几个例题后可以去岛屿数量上面试一下。

如果疑惑哪个元素会被重复进入，可以看看下图（有点丑😭），蓝色元素会被两个红色元素扩散重复进入。如果加上代码 2 就不会有这种情况。

三、例题练习

3.1 例题1：图像渲染

• 题目链接：图像渲染

• 问题描述：

有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小。

你也被给予三个整数 sr , sc 和 newColor 。你应该从像素 image[sr][sc] 开始对图像进行上色填充。

为了完成上色工作，从初始像素开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为 newColor 。

最后返回 经过上色渲染后的图像 。

• 解题思路：

可以利用深搜（DFS）或者宽搜（BFS），遍历到与该点相连的所有像素相同的点，然后将其修改成指定的像素即可。因为这个可以直接在原来数组上修改，那么我们就不用创建 vis 来标记我们已经走过的路，由于本文章主要讲解 BFS 所以本题采用 BFS 来进行解决。最后一个小优化，如果要修改的值和原来的值相同，那么直接返回即可。

• 代码编写：

class Solution {
    int[] dx = {0,0,-1,1};
    int[] dy = {1,-1,0,0};
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        if(image[sr][sc] == color){//处理边界情况
            return image;
        }
        int n = image.length;
        int m = image[0].length;
        int prev = image[sr][sc];
        Queue queue = new LinkedList<>();
        queue.add(new int[]{sr,sc});//创建队列
        while(!queue.isEmpty()){
            int[] tmp = queue.poll();
            int i = tmp[0],j = tmp[1];
            image[i][j] = color;
            for(int k = 0;k < 4;k++){
                int x = i + dx[k];
                int y = j + dy[k];
                if(x >= 0 && x < n && y >= 0 && y < m && image[x][y] == prev){
                    queue.offer(new int[]{x,y});
                }
            }
        }
        return image;
    }
}

3.2 例题2：岛屿数量

• 题目链接：岛屿数量

• 问题描述：

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

• 解题思路：

遍历整个矩阵，每次找到一块陆地的时候，岛屿数量 + 1，并且将这个陆地相连的所有陆地，全都修改，这样我们下次遍历到这里就不会影响最终的结果。当我们遍历完全部的矩阵的时候，岛屿数量也就找到了。

• 代码编写：

我们直接在原数据上修改，不用 vis 了。

class Solution {
    int[] dx = { 0, 0, 1, -1 };
    int[] dy = { 1, -1, 0, 0 };
    int n;
    int m;
    public int numIslands(char[][] grid) {
        int count = 0;// 最后统计岛屿数量
        n = grid.length;
        m = grid[0].length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '1') {//找到陆地
                    bfs(grid, i, j);//标记
                    count++;
                }
            }
        }
        return count;
    }
    public void bfs(char[][] grid, int i, int j) {
        Queue queue = new LinkedList<>();
        queue.add(new int[] { i, j });
        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int a = tmp[0];
            int b = tmp[1];
            grid[a][b] = '2';///1
            for (int k = 0; k < 4; k++) {
                int x = a + dx[k];
                int y = b + dy[k];
                if(x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == '1'){
                    queue.add(new int[]{x,y});
                     grid[x][y] = '2';///2
                }
            }
        }
    }
}

如果没有代码块 2 就会出现下面这种情况：超时啦！

3.3 例题3：岛屿的最大面积

• 题目链接：岛屿的最大面积

• 问题描述：

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直的四个方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

• 解题思路：

遍历整个矩阵，每当遇到一块土地的时候，就用深搜或者宽搜将与这块土地相连的整个岛屿的面积计算出来。然后在搜索得到的所有的岛屿面积求一个最大值即可。在搜索过程中，为了防止搜到重复的土地。也可以将原始矩阵的 1 修改成 2，当然我们也可以使用 vis 数组来保存我们走过的路。

• 代码编写：

class Solution {
    int n,m;
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    public int maxAreaOfIsland(int[][] grid) {
        int max = 0;
        n = grid.length;
        m = grid[0].length;
        for(int i = 0;i < n;i++){
            for(int j = 0;j < m;j++){
                if(grid[i][j] == 1){
                    max = Math.max(bfs(grid,i,j),max);//找出最大面积
                }
            }
        }
        return max;
    }
    public int bfs(int[][] grid,int i,int j){
        Queue queue = new LinkedList<>();
        queue.offer(new int[]{i,j});
        int count = 1;
        while(!queue.isEmpty()){
            int[] tmp = queue.poll();
            int a = tmp[0],b = tmp[1];
            grid[a][b] = 2;
            for(int k = 0;k < 4;k++){
                int x = a + dx[k];
                int y = b + dy[k];
                if(x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 1){
                    count++;
                    queue.offer(new int[]{x,y});
                    grid[x][y] = 2;//直接修改原数组的值即可。
                }
            }
        }
        return count;//返回岛屿的数量
    }
}

3.4 例题4：被围绕的区域

• 题目链接：被围绕的区域

• 问题描述：

给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

• 解题思路：

我们可以发现直接做难度还是挺大的，要处理的边界和各种条件还是比较多的，这里我们采用一种正难则反的思路来解决这道问题。

1. 先处理边界上的 O 区域，因为这个 O 一定不会是被围绕的，所以遍历边界来一次搜索即可。

2. 扫描矩阵，进行还原。

这题我们采用 vis 来标记我们走过的路。

• 代码编写：

class Solution {
    boolean[][] vis;
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    int n,m;
    public void solve(char[][] board) {
        n = board.length;m = board[0].length;
        vis = new boolean[n][m];
        //遍历边界
        for(int i = 0;i < m;i++){
            //第一行
            if(board[0][i] == 'O'){
                bfs(board,0,i);
            }
            //最后一行
            if(board[n - 1][i] == 'O'){
                bfs(board,n - 1,i);
            }
        }
        for(int i = 0;i < n;i++){
            //第一列
            if(board[i][0] == 'O'){
                bfs(board,i,0);
            }
            //最后一列
            if(board[i][m - 1] == 'O'){
                bfs(board,i,m - 1);
            }
        }
        //还原矩阵
        for(int i = 0;i < n;i++){
            for(int j = 0;j < m;j++){
                if(board[i][j] == 'O' && !vis[i][j]){
                    board[i][j] = 'X';
                }
            }
        }
    }
    public void bfs(char[][] board,int i,int j){
        vis[i][j] = true;
        Queue queue = new LinkedList<>();
        queue.offer(new int[]{i,j});
        while(!queue.isEmpty()){
            int[] tmp = queue.poll();
            int a = tmp[0];
            int b = tmp[1];
            for(int k = 0;k < 4;k++){
                int x = a + dx[k];
                int y = b + dy[k];
                if(x >= 0 && x < n && y >= 0 && y < m && board[x][y] == 'O' && !vis[x][y]){
                    queue.offer(new int[]{x,y});
                    vis[x][y] = true;
                }
            }
        }
    }
}