跳到主要内容

网格与状态图搜索解题框架

本节目标

用 DFS 遍历连通块，用 BFS 按层求无权状态图的最短步数。

网格中的一个格子、转盘上的一个四位字符串，都可以看作图中的一个状态；能一步到达的状态之间连一条边。区别不在于状态写成坐标还是字符串，而在于问题要找“能否连通、连通块有多大”，还是“最少走多少步”。

识别信号​

  • 只能从当前位置向固定方向移动，并且不能越界或穿过障碍；
  • 需要填满同色区域、统计一片陆地，或判断某个目标是否可达；
  • 每次操作代价相同，题目要求最少操作次数；
  • 状态没有显式边表，例如转动一位数字后得到的新字符串。

问题模型与核心不变量​

把每个可用状态视为节点，把一次合法移动视为边。网格只是节点坐标规律、邻居容易枚举的特殊图；转盘锁则在访问时即时生成字符串邻居。

DFS 沿一条路径深入，适合判断连通性、染色、遍历和递归汇总。对于图像渲染和岛屿面积，访问过的格子不会再作为另一条路径的候选，因此标记后不恢复：改色或沉岛就是永久访问。

回溯恰好不同。若同一格需要留给别的搜索分支再次使用，例如构造一条单词路径，递归返回前必须恢复现场。应先问“状态是否还能被其他解复用”，再决定访问标记是否恢复。

BFS 每次扩展同一层，首次到达的距离就是最短距离。关键不变量是：一个状态在入队时立即标记访问；若等到出队才标记，多个父状态可能在同一层反复把它放入队列。

通用模板​

DFS(row, col):
    若越界、障碍或已访问：返回题目要求的零值
    标记当前状态为已访问
    汇总当前状态与所有相邻状态的递归结果
    若题目要求路径可复用：返回前恢复标记
queue 加入起点
visited 立即加入起点
distance = 起点距离
while queue 非空:
    取出当前层全部状态
    对每个相邻状态：
        若合法且未访问：
            visited 立即加入相邻状态
            queue 加入相邻状态
    distance 增加一

模板变体​

  • 图像渲染以原颜色作为访问条件，改为目标颜色即完成标记；原颜色和目标颜色相同必须先返回。
  • 岛屿面积让 DFS 返回当前格贡献的 1 加上四个方向的面积，外层保留最大值。
  • 转盘锁把四位字符串作为状态，每一位向上、向下各产生一个邻居，共八条隐式边。
  • 二进制矩阵最短路径把 BFS 队列项扩展为 (row, col, distance)，并枚举八个方向；起点的距离为 1。

母题序列​

按必学顺序练习：

  1. 图像渲染：用同色 DFS 建立永久访问的最小模型。
  2. 岛屿的最大面积：让 DFS 返回并聚合一个连通块的面积。
  3. 打开转盘锁：把字符串操作转换为隐式状态图上的 BFS。
  4. 二进制矩阵中的最短路径：在网格中用八方向 BFS 求最短步数。

常见误区​

  • 把 DFS 的永久访问误写成回溯恢复，导致同一连通块被重复统计。
  • 反过来，在需要单条路径约束的问题里永久封锁格子，错过其他起点或分支。
  • BFS 到出队时才加入访问集合，使同一状态重复入队并放大队列。
  • 把 BFS 的层数从 0 和 1 混用，特别是单格起点就是终点时发生偏差。
  • 漏掉对角线方向，或把障碍格也加入队列。

迁移方向​

这一模型可继续迁移到多源 BFS、拓扑状态搜索、迷宫最短路和图的连通分量。先明确状态、邻接规则、访问语义和目标类型，再选择 DFS、BFS 或带恢复动作的回溯，能避免把“写法相似”的搜索混成同一种算法。