04 状态图 BFS 与图论建模
一、本阶段目标
学完本阶段，学生要能做到：
这是最贴近深圳自招的一章。因为自招题经常不会直接说“图”，而是给你一堆操作，让你求最少几步。
二、什么是状态图
普通图：
状态图：
例如：
题目：从数字 A 出发，每次可以 +1、-1、×2，问到 B 最少几步。
建模：
三、状态图 BFS 的四步法
只要这四个问题答清楚，代码就很容易写。
四、例题：奇怪的电梯模型
题意：有 n 层楼，第 i 层有一个数 k[i]。在第 i 层可以上 k[i] 层或下 k[i] 层，问从 A 到 B 最少按几次按钮。
建模：
代码框架：
五、什么时候需要多维状态
如果只记录当前位置不足以描述未来，就需要增加状态维度。
例如：迷宫中有钥匙。
状态应该是：
如果有 3 把钥匙，可以用二进制状态：
其中 mask 表示已经拿到哪些钥匙。
六、多维 BFS 模板
以 (x, y, state) 为例：
七、状态设计原则
状态不是越多越好。状态越多，复杂度越高。
设计状态时问自己：
如果一样，就可以合并成一个状态。
如果不一样，就需要增加状态维度。
例子：
八、状态图常见模型
题面 状态 转移 数字变换 当前数字 x +1、-1、×2 电梯上下 当前楼层 x x±k[x] 迷宫带钥匙 (x,y,钥匙集合) 上下左右 + 拿钥匙 机器人有方向 (x,y,dir) 前进、左转、右转 最多破一堵墙 (x,y,used) 走空地或破墙 颜色切换 (x,y,color) 换颜色或移动 剩余次数限制 (x,y,cnt) 使用特殊能力或不用
九、复杂度估算
BFS 的复杂度通常是：
例如：
如果 k 太大，状态压缩 BFS 就不可行。
十、和普通最短路的关系
状态图 BFS 本质上还是最短路：
如果操作代价不都是 1：
深圳自招阶段，先掌握“每步代价为 1 的状态 BFS”即可。
十一、课堂例题
例题 1：数字跳跃
从 A 到 B，每次可以 +1、-1、×2，不能超过范围 [0, MAX]，问最少几步。
状态：
转移：
例题 2：机器人转向
机器人在网格上，有朝向。每次可以前进一步、左转、右转，问到终点最少操作次数。
状态：
为什么要记录方向？
例题 3：最多破一堵墙
状态：
其中 used 表示是否已经破过墙。
如果只记录 (x,y) 会错，因为：
十二、练习题
题号 题名 训练点 建议 P1135 奇怪的电梯 一维状态 BFS 必做 P1746 离开中山路 二维网格状态 复习 P1126 机器人搬重物 位置 + 方向状态 提高 P1379 八数码难题 排列状态 BFS 提高 P2324 骑士精神 搜索状态建模，难度较高 冲刺
链接：
说明：P2324 难度明显高于深圳自招基础要求，适合强学生拓展。
十三、本阶段作业
1. 对 P1135 写出完整建模说明。
2. 完成 P1135。
3. 设计一道“数字变换”题，并写出状态和转移。
4. 选做 P1126，重点不是 AC，而是理解为什么状态要包含方向。
十四、本阶段小结
状态图 BFS 是自招建模的重点。
口诀：
