【BFS】《BFS 攻克 FloodFill：填平图形世界的技术密码》

---

前言

什么是BFS？

BFS（Breadth - First Search）算法，即广度优先搜索算法，是一种用于图或树结构的遍历算法。以下是其详细介绍：
算法原理：从给定的起始顶点开始，首先访问起始顶点，然后依次访问与起始顶点相邻的所有未被访问过的顶点，接着再以这些相邻顶点为基础，访问它们相邻的未访问顶点，以此类推，直到遍历完所有可达顶点或找到目标顶点。可以想象成以起始顶点为中心，一层一层地向外扩展访问。
实现方式：通常使用队列（Queue）数据结构来实现。先将起始顶点加入队列，然后不断取出队列头部的顶点进行访问，并将其未访问的相邻顶点加入队列，直到队列为空。
应用场景：常用于寻找图中两个顶点之间的最短路径、判断图的连通性、求解迷宫问题等。例如，在一个社交网络中，要查找从某个用户到另一个用户的最短关系链，就可以使用 BFS 算法。

FloodFill算法是什么问题呢？

问题描述：给定一个二维数组（可以表示图像的像素矩阵等），以及一个起始位置（种子点），还有要填充的颜色或值。算法的任务是从种子点开始，将与种子点相连通的具有相同颜色或值的区域，用新的颜色或值进行填充。例如，在图像编辑软件中，当使用油漆桶工具填充一个封闭区域时，就是 FloodFill 算法在起作用。

下面本篇文章将通过几个例题，带大家深入了解BFS和FloodFill问题

例题

一、 图像渲染

1. 题目链接： 图像渲染
2. 题目描述：

有⼀幅以 m x n 的⼆维整数数组表⽰的图画 image ，其中 image[i][j] 表⽰该图画的像素值⼤⼩。 你也被给予三个整数 sr , sc 和 newColor 。你应该从像素 image[sr][sc] 开始对图像进行上色填充 。
为了完成 上色⼯作 ，从初始像素开始，记录初始坐标的 上下左右四个方向上 像素值与初始坐标相同 的相连像素点，接着再记录这四个⽅向上符合条件的像素点与他们对应 四个方向上 像素值与初始坐 标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为 newColor 。 最后返回 经过上⾊渲染后的图像 。
示例1：
输⼊: image = [[1,1,1],[1,1,0],[1,0,1]]，sr = 1, sc = 1, newColor = 2 输出: [[2,2,2],[2,2,0],[2,0,1]]
解析: 在图像的正中间，(坐标(sr,sc)=(1,1)),在路径上所有符合条件的像素点的颜⾊都被更改成
注意，右下角的像素没有更改为 2，因为它不是在上下左右四个⽅向上与初始点相连的像素点
示例 2:
输⼊: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, newColor = 2 输出: [[2,2,2],[2,2,2]]

3. 算法思路：
   初始化：
   首先记录起始像素image[sr][sc]的原始颜色originalColor。
   创建一个队列queue，用于存储待处理的像素点。将起始像素点(sr, sc)加入队列。
   开始搜索：
   当队列不为空时，取出队列头部的像素点(x, y)。
   检查当前像素点(x, y)的颜色是否等于originalColor，如果不等于，则跳过该点（因为该点不属于需要填充的区域）。
   如果当前像素点的颜色等于originalColor，则将该像素点的颜色修改为color。
   然后检查当前像素点的上下左右四个相邻像素点(x - 1, y)、(x + 1, y)、(x, y - 1)、(x, y + 1)：
   确保相邻像素点在图像范围内（即0 <= x’ < m且0 <= y’ < n，其中x’和y’是相邻像素点的坐标）。
   确保相邻像素点的颜色等于originalColor（因为只有颜色相同的像素点才属于需要填充的区域）。
   如果满足上述条件，则将相邻像素点加入队列，等待后续处理。
   结束条件：当队列为空时，说明所有需要填充的像素点都已经处理完毕，此时返回修改后的图像image。

4. 代码示例：

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) {int prev = image[sr][sc];if(prev==color) return image;int m = image.length;int n = image[0].length;Queue<int[]> q = new LinkedList<>();q.add(new int[]{sr,sc});while(!q.isEmpty()){int[] t = q.poll();int a = t[0],b = t[1];image[a][b] = color;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.add(new int[]{x,y});}}}        return image;}
}

二、 岛屿数量

1. 题目链接：岛屿数量
2. 题目描述：

给你⼀个由 ‘1’（陆地）和 ‘0’（水）组成的的⼆维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由⽔平⽅向和/或竖直⽅向上相邻的陆地连接形成。 此外，你可以假设该网格的四条边均被水包围。
⽰例 1： 输⼊：grid = [
[“1”,“1”,“1”,“1”,“0”],
[“1”,“1”,“0”,“1”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“0”,“0”,“0”]
]
输出：1
示例 2：
输入：
grid = [
[“1”,“1”,“0”,“0”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“1”,“0”,“0”],
[“0”,“0”,“0”,“1”,“1”]
]输出：3
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 ‘0’ 或 ‘1’

3. 算法思路：
   遍历整个矩阵，每次找到「⼀块陆地」的时候：
   • 说明找到「⼀个岛屿」，记录到最终结果 ret 里面；
   • 并且将这个陆地相连的所有陆地，也就是这块「岛屿」，全部「变成海洋」。这样的话，我们下次遍历到这块岛屿的时候，它「已经是海洋」了，不会影响最终结果。
   • 其中「变成海洋」的操作，可以利用「深搜」和「宽搜」解决，其实就是上述图像渲染 这道题~

4. 代码示例：

class Solution {int[] dx={0,0,-1,1};int[] dy = {1,-1,0,0};int  m,n;boolean[][] vis = new boolean[301][301];public int numIslands(char[][] grid) {m = grid.length;n = grid[0].length;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;}public void bfs(char[][] grid,int i  ,int j){Queue<int[]> q = new LinkedList<>();q.add(new int[]{i,j});vis[i][j] =true;while(!q.isEmpty()){int[] t = q.poll();int a = t[0],b = t[1];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.add(new int[]{x,y});vis[x][y] = true;}}}}
}

三、岛屿的最大面积

1. 题目链接：岛屿的最大面积
2. 题目描述：

给你⼀个大小为 m x n 的⼆进制矩阵 grid 。
岛屿是由⼀些相邻的 1 (代表⼟地) 构成的组合，这⾥的「相邻」要求两个 1 必须在 ⽔平或者竖直的 四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表⽔）包围着。
岛屿的面积是岛上值为 1 的单元格的数⽬。 计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
示例 1：

输⼊：
grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出：6
解释：答案不应该是 11 ，因为岛屿只能包含⽔平或垂直这四个方向上的 1 。
示例 2： 输⼊：
grid = [[0,0,0,0,0,0,0,0]]
输出：0
提⽰：m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j] 为 0 或 1

3. 算法思路：
   • 遍历整个矩阵，每当遇到⼀块⼟地的时候，就⽤「深搜」或者「宽搜」将与这块⼟地相连的「整个岛屿」的⾯积计算出来。
   • 然后在搜索得到的「所有的岛屿⾯积」求⼀个「最⼤值」即可。
   • 在搜索过程中，为了「防⽌搜到重复的⼟地」： ◦ 可以开⼀个同等规模的「布尔数组」，标记⼀下这个位置是否已经被访问过；
   ◦ 也可以将原始矩阵的 1 修改成 0 ，但是这样操作会修改原始矩阵。

4. 代码示例：

class Solution {int m ,n;int[] dx = {0,0,1,-1};int[] dy = {1,-1,0,0};boolean[][] vis = new boolean[51][51];public int maxAreaOfIsland(int[][] grid) {m = grid.length;n = grid[0].length;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 =  Math.max(ret,bfs(grid,i,j));}}}return ret;}public int bfs(int[][] grid,int i ,int j){int count = 0;Queue<int[]> q = new LinkedList<>();q.add(new int[]{i,j});vis[i][j] = true;count++;while(!q.isEmpty()){int[] t = q.poll();int a = t[0],b = t[1];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.offer(new int[]{x,y});vis[x][y] = true;count++;}}}return count;}
}

四、被围绕的区域

1. 题目链接：被围绕的区域
2. 题目描述

给你⼀个 m x n 的矩阵 board ，由若⼲字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域 ⾥所有的 ‘O’ 用’X’ 填充。
示例 1：

输⼊：board = [[“X”,“X”,“X”,“X”],[“X”,“O”,“O”,“X”],[“X”,“X”,“O”,“X”],[“X”,“O”,“X”,“X”]]
输出：[[“X”,“X”,“X”,“X”],[“X”,“X”,“X”,“X”],[“X”,“X”,“X”,“X”],[“X”,“O”,“X”,“X”]]
解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
示例 2：
输入：board = [[“X”]]
输出：[[“X”]]
提示：
m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] 为 ‘X’ 或 'O

3. 解法：
   算法思路： 正难则反。 可以先利用 bfs 将与边缘相连的 ‘0’ 区域做上标记，然后重新遍历矩阵，将没有标记过的 '0’修改成 ‘X’ 即可。

4. 代码示例：

   class Solution {int[] dx = {0, 0, 1, -1};int[] dy = {1, -1, 0, 0};int m, n;public void solve(char[][] board) {m = board.length;n = board[0].length;// 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';}public void bfs(char[][] board, int i, int j) {Queue<int[]> q = new LinkedList<>();q.add(new int[]{i, j});board[i][j] = '.';while (!q.isEmpty()) {int[] t = q.poll();int a = t[0], b = t[1];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') {board[x][y] = '.';q.add(new int[]{x, y});}}}}}

结语

本文到这里就结束了，主要介绍了利用宽搜解决FloodFill算法问题，并通过例题深化了代码步骤，本篇文章题目十分考验代码能力，大家一定要自己尝试哦！

以上就是本文全部内容，感谢各位能够看到最后，创作不易，希望大家多多支持！

最后，大家再见！祝好！我们下期见！