BFS 解决 Flood Fill（图像渲染） 的思路
一、核心问题是什么？
Flood Fill 就是“从一个点出发，把和它连通、颜色相同的所有区域，全部改成目标颜色”。
BFS 解决这类问题，本质就是：用队列做“逐层扩散”，把连通区域里的点一个个找出来，再统一修改。
二、BFS 版 Flood Fill 核心思路（四步走）
步骤1：预处理，判断是否需要修改
先拿到起点 (sr, sc) 的初始颜色 prevColor，和目标颜色 newColor 比较：如果 prevColor == newColor：不用做任何修改，直接返回原图即可（避免无限循环）。
步骤2：初始化队列，把起点入队
创建一个队列，用来存待处理的像素坐标，把起点 (sr, sc) 加进去。
队列的作用是：按“先进先出”的顺序，逐层处理所有连通的点。
步骤3：BFS 循环，逐层扩散
只要队列不为空，就一直循环：
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 733）
1. 题目描述
2. 核心算法思路
本质是多源BFS（也可用DFS实现），通过队列逐层遍历连通区域：
1） 先记录起始像素的初始颜色 prevColor，若 prevColor == newColor，直接返回原图（无需修改）。
2） 将起始像素加入队列，标记为待处理。
3） 循环取出队首像素，将其颜色修改为 newColor，再检查其上下左右四个方向的像素：
若坐标合法（不越界）且颜色等于 prevColor，则加入队列等待处理。
4） 队列为空时，所有连通区域已完成染色，返回图像。
#include <vector> #include <queue> using namespace std; class Solution { // 定义坐标对，方便存储像素位置 typedef pair<int, int> PII; // 上下左右四个方向的坐标偏移量 int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; public: vector<vector<int>> floodFill(vector<vector<int>>& 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(); // 图像列数 queue<PII> q; // BFS队列 // 步骤2：起始像素入队 q.push({sr, sc}); // 步骤3：BFS遍历连通区域 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 200）
1. 题目描述
grid[i][j]的值为'0'或'1'
2. 核心算法思路
这道题是图像渲染的直接应用，核心逻辑是“遇到陆地就标记整个岛屿”：
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(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; } private: // BFS：将当前位置连通的所有陆地标记为已访问 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.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(vector<vector<int>>& 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(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()) { 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'或'O'
2. 核心算法思路：「正难则反」
如果直接找被包围的 '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(vector<vector<char>>& 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(vector<vector<char>>& board, int i, int j) { queue<pair<int, 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 数组，直接在原矩阵上修改，额外空间仅为队列占用。
