BFS 解决 FloodFill 算法（典型算法思想）—— OJ例题算法解析思路

目录

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

 算法代码：

 算法思路

基础参数

函数入口

检查条件

初始化 BFS

BFS 填充过程

返回结果

复杂度分析

总结

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

算法代码： 

算法思路

基础参数

函数入口

遍历网格

BFS 遍历

返回结果

复杂度分析

总结

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

算法代码：

算法思路

基础参数

函数入口

遍历网格

BFS 遍历

返回结果

复杂度分析

总结

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

算法代码： 

算法思路

基础参数

函数入口

处理边界上的 'O' 区域

还原棋盘

BFS 遍历

复杂度分析

总结

---

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

 算法代码：

class Solution {typedef pair<int, int> PII; // 定义坐标对int dx[4] = {0, 0, 1, -1}; // 四个方向的x偏移量int dy[4] = {1, -1, 0, 0}; // 四个方向的y偏移量public: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()) { // BFS循环auto [a, b] = q.front(); // 获取队首元素image[a][b] = color; // 将当前点的颜色设为目标颜色q.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 && image[x][y] == prev) {q.push({x, y}); // 将符合条件的坐标入队}}}return image; // 返回填充后的图像}
};

 算法思路

1. 基础参数

   • 使用 typedef pair<int, int> PII 定义一个坐标对，方便存储和操作点的坐标。

   • dx 和 dy 数组用于表示四个方向的移动（右、左、下、上）。

2. 函数入口

   • floodFill 函数接收一个图像 image（二维数组），起始坐标 sr 和 sc，以及要填充的颜色 color。

3. 检查条件

   • 首先获取起始点的原始颜色 prev，如果该颜色已经是目标颜色 color，则直接返回原图像，避免不必要的操作。

4. 初始化 BFS

   • 获取图像的尺寸 m 和 n。

   • 使用一个队列 q 来管理待处理的坐标。

   • 将起始坐标 (sr, sc) 入队。

5. BFS 填充过程

   • 进入循环，直到队列为空：

     • 从队列中取出当前坐标 (a, b)。

     • 将该坐标的颜色设置为 color。

     • 遍历四个方向，计算相邻坐标 (x, y)。

     • 检查新坐标是否在图像范围内，以及该坐标的颜色是否与 prev 相同。如果满足条件，则将新坐标入队。

6. 返回结果

   • 循环结束后，返回填充后的图像。

复杂度分析

• 时间复杂度：O(N)，N 为图像中像素的总数。在最坏情况下，所有像素都可能被访问。

• 空间复杂度：O(N)，队列在最坏情况下可能需要存储所有的像素。

总结

        这个实现有效地解决了洪水填充问题，通过广度优先搜索遍历所有与起始点相连的相同颜色区域并将其填充为目标颜色。可以根据需要调整该实现以适应更复杂的场景或者使用 DFS（深度优先搜索）来实现同样的功能。

 

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

算法代码： 

class Solution {int dx[4] = {1, -1, 0, 0}; // 表示上下左右的x偏移int dy[4] = {0, 0, 1, -1}; // 表示上下左右的y偏移bool vis[301][301]; // 记录访问状态int m, n; // 网格的行数和列数public: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); // 用BFS标记这个岛屿}}}return ret; // 返回岛屿总数}void bfs(vector<vector<char>>& grid, int i, int j) {queue<pair<int, int>> q; // 初始化队列q.push({i, j}); // 入队当前坐标vis[i][j] = true; // 标记为已访问while (q.size()) { // BFS循环auto [a, b] = q.front(); // 获取队首元素q.pop(); // 移除队首元素for (int k = 0; k < 4; k++) { // 遍历四个方向int x = a + dx[k], y = b + dy[k]; // 计算相邻坐标// 检查是否在边界内，并且为 '1' 且未访问if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' && !vis[x][y]) {q.push({x, y}); // 入队vis[x][y] = true; // 标记为已访问}}}}
};

算法思路

1. 基础参数

   • 使用 dx 和 dy 数组来表示四个方向的移动（上下左右）。

   • vis 数组用于标记已经访问过的网格，避免重复计算。

2. 函数入口

   • numIslands 函数接收一个二维网格 grid 作为输入，返回岛屿的数量。

3. 遍历网格

   • 计算网格的行数 m 和列数 n。

   • 使用双重循环遍历每个格子：

     • 当遇到 '1' 且未被访问过时，说明找到了一个新的岛屿，计数器 ret 加一，并调用 bfs 函数来遍历和标记这个岛屿的所有部分。

4. BFS 遍历

   • 在 bfs 函数中：

     • 初始化一个队列，将当前陆地坐标入队，并将其标记为已访问。

     • 进入循环，直到队列为空：

       • 从队列中取出当前坐标 (a, b)。

       • 遍历四个方向，计算相邻坐标 (x, y)。

       • 检查新坐标是否在网格范围内，且该坐标为 '1' 且未被访问过。如果满足条件，则将新坐标入队并标记为已访问。

5. 返回结果

   • 循环完成后，返回计数器 ret 的值，表示岛屿的总数量。

复杂度分析

• 时间复杂度：O(M * N)，其中 M 是行数，N 是列数。在最坏情况下，所有格子都可能被访问一次。

• 空间复杂度：O(M * N)，用于存储访问状态 vis，在最坏情况下，可能需要存储整个网格的状态。

总结

        这个实现有效地解决了“岛屿数量”问题，通过广度优先搜索（BFS）遍历所有相连的陆地（'1'），并将其标记为已访问，以避免重复计数。可以根据需要将 BFS 替换为深度优先搜索（DFS）以实现相同的功能。总之，该算法能够高效地计算出网格中的岛屿数量，尤其适用于处理大型的二维网格问题。

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

算法代码：

class Solution {int dx[4] = {0, 0, 1, -1}; // 表示上下左右的x偏移int dy[4] = {1, -1, 0, 0}; // 表示上下左右的y偏移bool vis[51][51]; // 记录访问状态（假设最大网格为51x51）int m, n; // 网格的行数和列数public:int maxAreaOfIsland(vector<vector<int>>& 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 = max(ret, bfs(grid, i, j)); // 计算岛屿面积并更新最大面积}}}return ret; // 返回最大岛屿面积}int bfs(vector<vector<int>>& grid, int i, int j) {int count = 0; // 初始化当前岛屿面积计数queue<pair<int, int>> q; // 初始化队列q.push({i, j}); // 入队当前坐标vis[i][j] = true; // 标记为已访问count++; // 当前岛屿面积增加while (q.size()) { // BFS循环auto [a, b] = q.front(); // 获取队首元素q.pop(); // 移除队首元素for (int k = 0; k < 4; k++) { // 遍历四个方向int x = a + dx[k], y = b + dy[k]; // 计算相邻坐标// 检查是否在边界内，并且为 '1' 且未访问if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !vis[x][y]) {q.push({x, y}); // 入队vis[x][y] = true; // 标记为已访问count++; // 增加岛屿面积}}}return count; // 返回当前岛屿的面积}
};

算法思路

1. 基础参数

   • dx 和 dy 数组用来表示四个方向的移动（右、左、下、上）。

   • vis 数组用于标记已经访问过的格子，以避免重复计算。

2. 函数入口

   • maxAreaOfIsland 函数接收一个二维网格 grid 作为输入，返回最大的岛屿面积。

3. 遍历网格

   • 计算网格的行数 m 和列数 n。

   • 使用双重循环遍历每个格子：

     • 当遇到 1（陆地）且未被访问过时，调用 bfs 函数来计算这个岛屿的面积，并更新最大面积 ret。

4. BFS 遍历

   • 在 bfs 函数中：

     • 初始化一个计数器 count 用于记录岛屿的面积。

     • 将当前陆地坐标入队，并标记为已访问，同时将 count 增加。

     • 进入循环，直到队列为空：

       • 从队列中取出当前坐标 (a, b)。

       • 遍历四个方向，计算相邻坐标 (x, y)。

       • 检查新坐标是否在网格范围内，且该坐标为 1 且未被访问过。如果满足条件，则将新坐标入队并标记为已访问，同时增加 count。

5. 返回结果

   • 循环完成后，返回最大的岛屿面积 ret。

复杂度分析

• 时间复杂度：O(M * N)，其中 M 是行数，N 是列数。在最坏情况下，所有格子都可能被访问一次。

• 空间复杂度：O(M * N)，用于存储访问状态 vis，在最坏情况下，可能需要存储整个网格的状态。

总结

        这个实现有效地解决了“最大岛屿面积”问题，通过广度优先搜索（BFS）遍历所有相连的陆地（1），并计算其面积。该算法能够高效地找到最大的岛屿面积，尤其适用于处理大型的二维网格问题。如果需要，也可以将 BFS 替换为深度优先搜索（DFS）以实现相同的功能。总之，该算法能够在给定的网格中快速找到并计算最大岛屿的面积。

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

算法代码： 

class Solution {int dx[4] = {0, 0, 1, -1}; // 表示上下左右的x偏移int dy[4] = {1, -1, 0, 0}; // 表示上下左右的y偏移int m, n; // 棋盘的行数和列数public:void solve(vector<vector<char>>& board) {m = board.size(); // 获取行数n = board[0].size(); // 获取列数// 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') // 被围住的区域变为 'X'board[i][j] = 'X';else if (board[i][j] == '.') // 安全的区域还原为 'O'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()) { // BFS循环auto [a, b] = q.front(); // 获取队首元素q.pop(); // 移除队首元素for (int k = 0; k < 4; k++) { // 遍历四个方向int x = a + dx[k], y = b + dy[k]; // 计算相邻坐标// 检查是否在边界内，并且为 'O'if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O') {q.push({x, y}); // 入队board[x][y] = '.'; // 标记为已访问（安全）}}}}
};

算法思路

1. 基础参数

   • dx 和 dy 数组用来表示四个方向的移动（上下左右）。

   • m 和 n 分别表示棋盘的行数和列数。

2. 函数入口

   • solve 函数接收一个二维棋盘 board，用于处理其中的 'O' 区域。

3. 处理边界上的 'O' 区域

   • 通过双重循环遍历棋盘的边界（第一行、最后一行、第一列、最后一列）：

     • 当遇到 'O' 时，调用 bfs 函数，将其和与之相连的所有 'O' 修改为 '.'，表示这些 'O' 是安全的，不会被围住。

4. 还原棋盘

   • 遍历整个棋盘，将剩余的 'O' （被围住的）改为 'X'，将 '.' 还原为 'O'。

5. BFS 遍历

   • 在 bfs 函数中：

     • 初始化一个队列，将当前坐标入队，并将其改为 '.'。

     • 进入循环，直到队列为空：

       • 从队列中取出当前坐标 (a, b)。

       • 遍历四个方向，计算相邻坐标 (x, y)。

       • 检查新坐标是否在棋盘范围内，且该坐标为 'O'，如果满足条件，则将新坐标入队并改为 '.'。

复杂度分析

• 时间复杂度：O(M * N)，其中 M 是行数，N 是列数。在最坏情况下，所有格子都可能被访问一次。

• 空间复杂度：O(M * N)，用于存储队列和处理访问状态，尤其当整个棋盘都是 'O' 时，队列可能存储整个棋盘。

总结

        这个实现有效地解决了“被围绕的区域”问题，通过广度优先搜索（BFS）遍历所有与边界相连的 'O'，并将其标记为安全区域。最终，该算法能够高效地将被围住的区域转变为 'X'，而保证与边界相连的 'O' 区域保持不变。该算法非常适合处理类似的二维网格问题，通过 BFS 的方式可以灵活地处理不同的边界条件和连通性问题。