FloodFill算法---BFS

一、前言

二、算法模板套路

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<int[]> 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;///1for (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<int[]> 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<int[]> 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';///1for (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<int[]> 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<int[]> 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;}}}}
}