【算法-BFS实现FloodFill算法】使用BFS实现FloodFill算法：高效识别连通块并进行图像填充

算法	相关知识点	可以通过点击	以下链接进行学习	一起加油！
双指针	滑动窗口	二分查找	前缀和	位运算
模拟	链表	哈希表	字符串模拟	栈模拟(非单调栈)
优先级队列	队列 & BFS

在图论中，最短路径问题是一个常见的挑战，广泛应用于路由、网络和交通等领域。对于无权图，广度优先搜索（BFS）提供了一种高效且简洁的解法。本文将简要介绍BFS算法的原理，并探讨其在解决最短路径问题中的应用。

🌈个人主页：是店小二呀
🌈C/C++专栏：C语言\ C++
🌈初/高阶数据结构专栏： 初阶数据结构\ 高阶数据结构
🌈Linux专栏： Linux
🌈算法专栏：算法
🌈Mysql专栏:Mysql

🌈你可知:无人扶我青云志 我自踏雪至山巅

733. 图像渲染

【题目】：733. 图像渲染

【算法思路】

可以通过深度优先搜索（DFS）或广度优先搜索（BFS），遍历所有与该点相连且像素值相同的点，并将它们的像素值修改为指定的值。

首先，使用变量记录目标像素值，并处理边界情况。在FloodFill算法中，借助队列实现广度优先搜索（BFS）。队列中的元素类型应为pair<int, int>，用于存储坐标。为了简化代码，可以通过typedef对其进行类型重定义。

队列的特性是先进先出（FIFO），因此当前节点在广度优先搜索（BFS）中出队后，周围的节点会依次入队。为了遍历上下左右的相邻位置，单纯依赖队列还不足够，需要添加位置偏移量来处理相邻节点。通过设置上下左右的偏移量，调整 dx 和 dy 数组，当相邻节点符合条件时，表示它们属于同一连接区域，并将其入队进行进一步处理。

以下是一个使用BFS（广度优先搜索）实现Flood Fill算法的模板，适用于类似FloodFill的问题：

【代码实现】

class Solution {
public:typedef pair<int, int> PII;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};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();q.pop();image[a][b] = color;for(int i = 0; i < 4; i++){int x = a + dx[i];int y = b + dy[i];if(x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev){q.push({x,y});}}    }return image;}
};

---

200. 岛屿数量

【题目】：200. 岛屿数量

【算法思路】

解决此类FloodFill算法问题时，通常采用BFS或DFS。该题的算法思路是遍历矩阵并使用BFS算法，在遍历过程中统计岛屿的数量，可以通过一个变量判断每次第一次遇到岛屿。

这里需要使用 vis[m][n] 数组来记录每个岛屿的陆地是否已经经过BFS遍历，避免重复访问。另一种方式是直接修改原数组（例如将访问过的陆地标记为水），但这样做可能会影响原始数据，因此在面试过程中，建议首先询问面试官是否可以直接修改原数组。

将变量设为全局变量，可以更加方便使用。

【代码实现】

class Solution {
public:int dx[4] = {1, -1, 0, 0};int dy[4] = {0, 0, 1, -1};typedef pair<int, int> PII;int vis[301][301];int m, n;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<PII> q;q.push({i, j});vis[i][j] = true;while(!q.empty()){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 && !vis[x][y] && grid[x][y] == '1'){q.push({x,y});vis[x][y] = true;}}}}
};

---

695. 岛屿的最大面积

【题目】：695. 岛屿的最大面积

【算法思路】

与"200. 岛屿数量"题目类似，主要步骤相同，但在这道题中，重点是使用一个变量记录BFS遍历过程中遇到的"陆地数量"。通过BFS或DFS遍历每个岛屿，遇到的每个陆地（‘1’）会被标记为已访问，并且可以使用一个计数器统计陆地的数量。

【代码实现】

class Solution {
public:int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};bool vis[51][51];int m, n;int maxAreaOfIsland(vector<vector<int>>& grid) {m = grid.size(), n = grid[0].size();int ret = 0;//1.进行遍历矩阵操作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 partCount = 0;queue<pair<int, int>> q;q.push({i, j});vis[i][j] = true;partCount++;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;partCount++;}}}return partCount;}
};

---

130. 被围绕的区域

【题目】：130. 被围绕的区域

【算法思路】

如果直接使用 BFS 进行搜索较为复杂，不如采用 正难则反 的思路：先处理边界上的 O 区域，再扫描矩阵并逐步还原。对于这类问题，关键在于提前理清步骤，并注意细节问题的处理。

在修改后的矩阵中，BFS 过程中不再需要额外的 vis 数组来处理重复遍历。通过直接在矩阵中修改元素（例如将已访问的元素标记为某个特殊值），我们可以避免重复访问，从而简化算法。这样一来，矩阵本身就充当了“访问标记”的角色，无需额外的空间开销来跟踪节点的访问状态。

【代码实现】

class Solution {
public:int dx[4] = {1, -1, 0, 0};int dy[4] = {0, 0, 1, -1};int m, n;void solve(vector<vector<char>>& board) {m = board.size(), n = board[0].size();//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);}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] = '.';}}}}
};

快和小二一起踏上精彩的算法之旅！关注我，我们将一起破解算法奥秘，探索更多实用且有趣的知识，开启属于你的编程冒险！