—— 基于迷宫问题与消消乐连通块统计的工程实践
一、BFS 基本概念
广度优先搜索（BFS，Breadth-First Search） 是一种按“层级”向外扩展的图遍历算法。
其核心特征是：
从起点出发，先访问所有距离为 1 的节点，再访问距离为 2 的节点，以此类推。
BFS 通常依赖 队列（Queue） 实现，天然具备以下优势：
- 遍历顺序稳定
- 不会出现递归栈溢出
- 非常适合：
- 最短路径
- 连通块统计
- 大规模网格搜索
二、BFS 在二维网格问题中的通用模型
1. 网格抽象为图
- 每个格子：一个节点
- 上下左右：边
- 是否可扩展：由题目规则决定（颜色是否相同、是否不同等）
2. BFS 通用模板（二维网格）
Queue<Node> queue = new Queue<Node>();
queue.Enqueue(start);
mark[start] = true;while (queue.Count > 0)
{Node cur = queue.Dequeue();for (四个方向){if (合法 && 未访问 && 满足条件){mark[next] = true;queue.Enqueue(next);}}
}
三、BFS 示例一：迷宫 01 交替连通块问题
1. 问题描述
- 给定一个
n × n的迷宫 - 每个格子为
'0'或'1' - 连通条件：
- 上下左右相邻
- 相邻格子的值必须不同（01 交替）
- 多次查询某个格子所在连通块的大小
2. 设计目标
- 对迷宫进行一次 BFS 预处理
- 标记所有 01 交替的连通块
- 查询阶段 O(1) 返回答案
3. 核心数据结构
char[,] grid; // 迷宫地图
int[,] compId; // 每个格子的连通块编号
int[] compSize; // 每个连通块的大小
含义说明：
compId[x][y] = k：该格子属于第 k 个连通块compSize[k]：第 k 个连通块的格子数量
4. BFS 核心实现逻辑
static void BFS(int sx, int sy, int id)
{Queue<Point> queue = new Queue<Point>();queue.Enqueue(new Point(sx, sy));compId[sx, sy] = id;compSize[id] = 1;while (queue.Count > 0){Point p = queue.Dequeue();for (int i = 0; i < 4; i++){int nx = p.x + dx[i];int ny = p.y + dy[i];if (nx < 0 || nx >= n || ny < 0 || ny >= n)continue;// 01 交替 + 未访问if (grid[p.x, p.y] != grid[nx, ny] && compId[nx, ny] == 0){compId[nx, ny] = id;compSize[id]++;queue.Enqueue(new Point(nx, ny));}}}
}
5. 算法本质分析
- BFS 扩展的是 “合法的相邻状态”
- 连通块的定义只体现在 扩展条件
- BFS 本身不关心业务规则
四、BFS 示例二：消消乐连通块统计（同色）
1. 问题描述
- 棋盘为
n × n - 每个格子有一个颜色（整数）
- 消除规则：
- 上下左右相邻
- 颜色相同
- 多次点击，询问消除数量
2. 核心优化思想：预处理 + 查询分离
如果每次点击都 BFS：
- 单次：
O(n²) - m 次：
O(mn²)（不可接受）
解决方案：
使用 BFS 对所有连通块进行一次性预处理。
3. BFS 预处理流程
for 每一个格子 (i, j)if compId[i][j] == 0compCnt++BFS(i, j, compCnt)
4. BFS 实现代码（同色连通）
static void BFS(int sx, int sy, int id)
{Queue<Pos> queue = new Queue<Pos>();queue.Enqueue(new Pos(sx, sy));compId[sx, sy] = id;compSize[id] = 1;while (queue.Count > 0){Pos p = queue.Dequeue();for (int i = 0; i < 4; i++){int nx = p.x + dx[i];int ny = p.y + dy[i];if (nx < 0 || nx >= n || ny < 0 || ny >= n)continue;if (grid[p.x, p.y] == grid[nx, ny] && compId[nx, ny] == 0){compId[nx, ny] = id;compSize[id]++;queue.Enqueue(new Pos(nx, ny));}}}
}
5. 查询阶段（O(1)）
int id = compId[x][y];
Console.WriteLine(compSize[id]);
五、BFS 连通块模型统一总结
1. 抽象结构
| 元素 | 含义 |
|---|---|
| 节点 | 网格中的格子 |
| 边 | 上下左右 |
| 扩展条件 | 颜色相同 / 不同 |
| 连通块 | 满足规则的最大集合 |
2. BFS 与 DFS 在工程中的选择
| 对比项 | BFS | DFS |
|---|---|---|
| 是否递归 | 否 | 是 |
| 栈溢出风险 | 无 | 有 |
| 稳定性 | 高 | 中 |
| 大规模网格 | 更适合 | 有风险 |
六、复杂度分析
设 N = n × n
- 预处理时间复杂度：
O(N) - 单次查询时间复杂度：
O(1) - 总时间复杂度：
O(N + m) - 空间复杂度：
O(N)
七、核心认知总结
BFS 的真正价值不在“搜索”，而在：
用一次完整遍历，换取所有查询的常数时间响应
当你开始自然使用：
compIdcompSize- “预处理 + 查询分离”
说明你已经掌握了 工程级 BFS 思维。
八、一句话模板总结
凡是：网格 + 连通规则 + 多次查询
第一反应：BFS / DFS 预处理连通块