BFS 解决 Flood Fill图像渲染 的思路一、核心问题是什么Flood Fill 就是“从一个点出发把和它连通、颜色相同的所有区域全部改成目标颜色”。BFS 解决这类问题本质就是用队列做“逐层扩散”把连通区域里的点一个个找出来再统一修改。二、BFS 版 Flood Fill 核心思路四步走步骤1预处理判断是否需要修改先拿到起点 (sr, sc) 的初始颜色 prevColor和目标颜色 newColor 比较如果 prevColor newColor不用做任何修改直接返回原图即可避免无限循环。步骤2初始化队列把起点入队创建一个队列用来存待处理的像素坐标把起点 (sr, sc) 加进去。队列的作用是按“先进先出”的顺序逐层处理所有连通的点。步骤3BFS 循环逐层扩散只要队列不为空就一直循环1. 取出队首像素 (a, b)。2. 修改颜色把 image[a][b] 改成 newColor。3. 遍历四个方向上下左右得到新坐标 (x, y)检查 (x, y) 是否越界不能小于0不能超过矩阵行列数。检查 image[x][y] 是否等于初始颜色 prevColor。如果两个条件都满足说明它和起点连通把 (x, y) 加入队列等待下一轮处理。步骤4循环结束返回结果队列为空时说明所有连通的同色像素都已经被修改完成直接返回 image 即可。三、关键细节拆解为什么这么写1. 为什么要先存 prevColor因为你要修改颜色如果不提前存好初始颜色当你把第一个点改成 newColor 后后面的判断条件 image[x][y] prevColor 就失效了会漏掉连通区域。2. 为什么修改颜色要在出队时做入队时只做“标记待处理”出队时再修改保证每个点只被处理一次。如果入队就修改也可以但要注意不要重复入队同一个点BFS里坐标不重复入队是关键。3. 为什么要判断 prevColor newColor如果起点颜色和目标颜色一样直接修改会导致队列无限循环因为所有点都满足条件一直入队所以要提前剪枝。四、伪代码帮你直观理解流程function floodFill(image, sr, sc, newColor): prevColor image[sr][sc] if prevColor newColor: return image m image行数, n image列数 创建队列 q q.push( (sr, sc) ) while q 不为空: (a, b) q.pop() image[a][b] newColor // 修改当前点颜色 for 四个方向 (上下左右): x a dx[k] y b dy[k] if x、y 合法 且 image[x][y] prevColor: q.push( (x, y) ) return image五、复杂度分析设图像大小为 m × n时间复杂度O(m × n)每个像素最多被入队、出队各一次所有操作都是线性的。空间复杂度O(m × n)最坏情况整个图像同色队列最多存 m × n 个像素平均情况是连通区域的大小。题目1图像渲染LeetCode 7331. 题目描述2. 核心算法思路本质是多源BFS也可用DFS实现通过队列逐层遍历连通区域1 先记录起始像素的初始颜色 prevColor若 prevColor newColor直接返回原图无需修改。2 将起始像素加入队列标记为待处理。3 循环取出队首像素将其颜色修改为 newColor再检查其上下左右四个方向的像素若坐标合法不越界且颜色等于 prevColor则加入队列等待处理。4 队列为空时所有连通区域已完成染色返回图像。#include vector #include queue using namespace std; class Solution { // 定义坐标对方便存储像素位置 typedef pairint, int PII; // 上下左右四个方向的坐标偏移量 int dx[4] {0, 0, 1, -1}; int dy[4] {1, -1, 0, 0}; public: vectorvectorint floodFill(vectorvectorint image, int sr, int sc, int color) { // 步骤1记录初始颜色避免重复修改 int prevColor image[sr][sc]; if (prevColor color) return image; int m image.size(); // 图像行数 int n image[0].size(); // 图像列数 queuePII q; // BFS队列 // 步骤2起始像素入队 q.push({sr, sc}); // 步骤3BFS遍历连通区域 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] prevColor) { q.push({x, y}); } } } // 步骤4返回修改后的图像 return image; } };3. 复杂度分析设图像大小为 m × n行数m列数n。1时间复杂度O(m × n)核心逻辑每个像素最多被访问一次入队/出队各一次一旦被修改为新颜色就不会再被处理。最坏情况整个图像的像素都和起始像素同色需要遍历全部 m×n 个像素时间复杂度为 O(m×n)。2空间复杂度BFS实现队列O(m × n)最坏情况全图同色队列最多存储 m×n 个元素比如图像是一条直线队列需要存储所有节点。平均情况队列大小为连通区域的大小一般远小于 m×n。题目2岛屿数量LeetCode 2001. 题目描述grid[i][j]的值为0或12. 核心算法思路这道题是图像渲染的直接应用核心逻辑是“遇到陆地就标记整个岛屿”1 遍历整个二维网格遇到未访问的陆地grid[i][j] 1说明发现了一个新岛屿岛屿计数1。2 用BFS/DFS将该岛屿所有连通的陆地标记为已访问或直接修改为0避免重复统计。3 遍历完成后计数结果即为岛屿总数。#include vector #include queue using namespace std; class Solution { // 上下左右四个方向的坐标偏移量 int dx[4] {1, -1, 0, 0}; int dy[4] {0, 0, 1, -1}; bool vis[301][301]; // 标记已访问的陆地网格最大300×300 int m, n; // 网格的行数、列数 public: int numIslands(vectorvectorchar 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; } private: // BFS将当前位置连通的所有陆地标记为已访问 void bfs(vectorvectorchar grid, int i, int j) { queuepairint, int 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]; int 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; } } } } };3. 复杂度分析设网格大小为 m × n。1 时间复杂度O(m × n)核心逻辑每个单元格最多被访问一次要么是水要么是已访问的陆地。外层遍历网格的时间是O(m×n)每个陆地单元格只会被BFS/DFS处理一次因此总时间复杂度为 O(m×n)。2 空间复杂度BFS实现队列vis数组O(m × n)vis数组占用 m×n 空间。队列最坏情况下存储整个网格的陆地全是陆地额外空间为O(m×n)。优化可以不用vis数组直接把访问过的陆地改为0此时额外空间仅为队列的大小最坏仍为O(m×n)。4. BFS关键知识点队列的作用存储待处理的节点实现“先进先出”的逐层遍历避免递归栈溢出问题。方向数组用dx[4]和dy[4]统一表示上下左右四个方向简化代码逻辑。边界检查遍历相邻节点时必须检查坐标是否越界x 0 x m y 0 y n避免访问非法内存。去重处理图像渲染通过“修改颜色”避免重复处理同一像素岛屿数量通过vis数组或直接修改grid为0避免重复统计同一岛屿。题目3岛屿的最大面积LeetCode 695这道题是前面「岛屿数量」的进阶版核心逻辑还是四连通BFS/DFS区别在于岛屿数量统计连通分量的个数 岛屿的最大面积统计每个连通分量的大小并取最大值1. 题目描述2. 核心算法思路1) 遍历整个矩阵逐个检查每个单元格。2) 遇到未访问的陆地grid[i][j] 1启动BFS/DFS遍历该岛屿所有连通的陆地同时统计岛屿面积。为避免重复统计要么用vis数组标记已访问要么直接将访问过的1改为0。3) 更新最大面积每次统计完一个岛屿的面积后和当前最大值比较并更新。4) 遍历完成后返回记录的最大面积即可。class Solution { int m, n; int dx[4] {0, 0, 1, -1}; int dy[4] {1, -1, 0, 0}; bool vis[51][51]; public: int maxAreaOfIsland(vectorvectorint grid) { int ret 0; m grid.size(), n grid[0].size(); 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(vectorvectorint grid, int i, int j) { int count 0; queuepairint, int q; q.push({i, j}); vis[i][j] true; count; 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; count; } } } return count; } };3. 复杂度分析设网格大小为 m × n。1) 时间复杂度O(m × n)每个单元格最多被访问一次要么是水要么是已访问的陆地外层遍历BFS的总时间为线性。2)空间复杂度O(m × n)vis数组占用 m×n 空间BFS队列最坏情况下存储整个网格的陆地全为陆地额外空间为O(m×n)优化可以不用vis数组直接把访问过的1改为0此时额外空间仅为队列的大小最坏仍为O(min(m,n))队列按层存储最大为网格的最短边长度。题目4被围绕的区域LeetCode 130这道题和前面的BFS题是同一套模板但解题思路用了逆向思维非常巧妙。1. 题目描述提示m board.lengthn board[i].length1 m, n 200board[i][j]为X或O2. 核心算法思路「正难则反」如果直接找被包围的 O需要判断每个区域是否和边界连通逻辑复杂且容易出错。因此采用逆向思维1 标记安全的 O遍历矩阵的四条边界遇到 O 就启动BFS/DFS将所有和边界连通的 O 标记为临时字符如 .表示它们是“安全的”不会被填充。2 统一修改矩阵遍历整个矩阵遇到未标记的 O说明它被 X 包围改为 X。遇到临时标记 .恢复为原来的 O。#include vector #include queue using namespace std; class Solution { // 上下左右四个方向的坐标偏移量 int dx[4] {0, 0, 1, -1}; int dy[4] {1, -1, 0, 0}; int m, n; // 矩阵的行数、列数 public: void solve(vectorvectorchar board) { m board.size(); if (m 0) return; n board[0].size(); // 1. 处理四条边界上的O标记所有与边界连通的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 1; i m-1; 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) { // 未被标记的O是被包围的区域改为X board[i][j] X; } else if (board[i][j] .) { // 标记过的安全区域恢复为O board[i][j] O; } } } } private: // BFS将当前O及所有连通的O标记为. void bfs(vectorvectorchar board, int i, int j) { queuepairint, int q; q.push({i, j}); board[i][j] .; // 标记为安全 while (!q.empty()) { auto [a, b] q.front(); q.pop(); // 遍历四个方向 for (int k 0; k 4; k) { int x a dx[k]; int 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] .; } } } } };3. 复杂度分析设矩阵大小为 m × n时间复杂度O(m × n) 边界遍历BFS标记的总时间为线性每个单元格最多被访问一次 最后的矩阵遍历也是 O(m × n)总时间复杂度为线性。空间复杂度O(m × n)BFS队列最坏情况下存储整个矩阵的边界连通区域空间复杂度为 O(min(m, n))队列按层存储最大为矩阵的最短边长度无需额外的 vis 数组直接在原矩阵上修改额外空间仅为队列占用。