04 状态图 BFS 与图论建模
2026-06-30 18:53:21
发布于：广东
2阅读
0回复
0点赞
04 状态图 BFS 与图论建模
一、本阶段目标
学完本阶段，学生要能做到：
1. 理解“状态也可以作为点”。
2. 能把操作题转化成图论题。
3. 会设计状态、转移和边界。
4. 能用 BFS 求最少操作次数。
5. 能判断什么时候需要多维状态。
这是最贴近深圳自招的一章。因为自招题经常不会直接说“图”，而是给你一堆操作，让你求最少几步。
二、什么是状态图
普通图：
点是城市、格子、文章。
边是道路、相邻、引用。
状态图：
点是“当前局面”。
边是“一次合法操作”。
例如：
题目：从数字 A 出发，每次可以 +1、-1、×2，问到 B 最少几步。
建模：
点：每一个数字 x
边：x -> x+1, x -> x-1, x -> 2x
每条边代价：1
答案：A 到 B 的最短路
算法：BFS
三、状态图 BFS 的四步法
1. 状态是什么？
2. 初始状态是什么？
3. 目标状态是什么？
4. 从一个状态可以转移到哪些状态？
只要这四个问题答清楚，代码就很容易写。
四、例题：奇怪的电梯模型
题意：有 n 层楼，第 i 层有一个数 k[i]。在第 i 层可以上 k[i] 层或下 k[i] 层，问从 A 到 B 最少按几次按钮。
建模：
状态：当前楼层 x
初始状态：A
目标状态：B
转移：x -> x + k[x]，x -> x - k[x]
边权：每按一次按钮，代价为 1
算法：BFS
代码框架：
queue<int> q;
memset(dist, -1, sizeof(dist));
dist[A] = 0;
q.push(A);
while (!q.empty()) {
int x = q.front();
q.pop();
int nxt1 = x + k[x];
int nxt2 = x - k[x];
if (1 <= nxt1 && nxt1 <= n && dist[nxt1] == -1) {
dist[nxt1] = dist[x] + 1;
q.push(nxt1);
}
if (1 <= nxt2 && nxt2 <= n && dist[nxt2] == -1) {
dist[nxt2] = dist[x] + 1;
q.push(nxt2);
}
}
五、什么时候需要多维状态
如果只记录当前位置不足以描述未来，就需要增加状态维度。
例如：迷宫中有钥匙。
只知道人在 (x,y) 不够。
还要知道有没有钥匙。
状态应该是：
(x, y, hasKey)
如果有 3 把钥匙，可以用二进制状态：
(x, y, mask)
其中 mask 表示已经拿到哪些钥匙。
六、多维 BFS 模板
以 (x, y, state) 为例：
struct Node {
int x, y, s;
};
int dist[N][N][S];
queue<Node> q;
memset(dist, -1, sizeof(dist));
dist[sx][sy][0] = 0;
q.push({sx, sy, 0});
while (!q.empty()) {
auto cur = q.front();
q.pop();
for (int k = 0; k < 4; k++) {
int nx = cur.x + dx[k];
int ny = cur.y + dy[k];
int ns = cur.s;
if (!inside(nx, ny)) continue;
if (wall[nx][ny]) continue;
// 根据格子内容修改 ns
// if (a[nx][ny] == 'K') ns |= 1;
if (dist[nx][ny][ns] == -1) {
dist[nx][ny][ns] = dist[cur.x][cur.y][cur.s] + 1;
q.push({nx, ny, ns});
}
}
}
七、状态设计原则
状态不是越多越好。状态越多，复杂度越高。
设计状态时问自己：
如果两个局面有相同的状态表示，它们后续能做的事情是否完全一样？
如果一样，就可以合并成一个状态。
如果不一样，就需要增加状态维度。
例子：
人在同一格子，但有没有钥匙会影响能不能开门。
所以钥匙必须进状态。
人在同一格子，但已经走了哪条具体路线不影响未来。
所以路线不需要进状态。
八、状态图常见模型
| 题面 | 状态 | 转移 |
|---|---|---|
| 数字变换 | 当前数字 x | +1、-1、×2 |
| 电梯上下 | 当前楼层 x | x±k[x] |
| 迷宫带钥匙 | (x,y,钥匙集合) | 上下左右 + 拿钥匙 |
| 机器人有方向 | (x,y,dir) | 前进、左转、右转 |
| 最多破一堵墙 | (x,y,used) | 走空地或破墙 |
| 颜色切换 | (x,y,color) | 换颜色或移动 |
| 剩余次数限制 | (x,y,cnt) | 使用特殊能力或不用 |
九、复杂度估算
BFS 的复杂度通常是：
状态数量 × 每个状态的转移数量
例如：
n × m 的迷宫，4 个方向：O(nm)
n × m 的迷宫，钥匙状态 2^k，4 个方向：O(nm2^k)
如果 k 太大，状态压缩 BFS 就不可行。
十、和普通最短路的关系
状态图 BFS 本质上还是最短路：
每个状态是点
每次操作是边
每条边代价为 1
求最少操作次数就是 BFS
如果操作代价不都是 1：
边权只有 0 和 1：0-1 BFS
边权非负：Dijkstra
有负权：Bellman-Ford/SPFA 或其他模型
深圳自招阶段，先掌握“每步代价为 1 的状态 BFS”即可。
十一、课堂例题
例题 1：数字跳跃
从 A 到 B，每次可以 +1、-1、×2，不能超过范围 [0, MAX]，问最少几步。
状态：
当前数字 x
转移：
x + 1
x - 1
x * 2
例题 2：机器人转向
机器人在网格上，有朝向。每次可以前进一步、左转、右转，问到终点最少操作次数。
状态：
(x, y, dir)
为什么要记录方向？
因为人在同一格子但朝向不同，下一步能前进的方向不同。
例题 3：最多破一堵墙
状态：
(x, y, used)
其中 used 表示是否已经破过墙。
如果只记录 (x,y) 会错，因为：
到达同一个格子时，是否还保留破墙机会，会影响后续能不能走。
十二、练习题
| 题号 | 题名 | 训练点 | 建议 |
|---|---|---|---|
| P1135 | 奇怪的电梯 | 一维状态 BFS | 必做 |
| P1746 | 离开中山路 | 二维网格状态 | 复习 |
| P1126 | 机器人搬重物 | 位置 + 方向状态 | 提高 |
| P1379 | 八数码难题 | 排列状态 BFS | 提高 |
| P2324 | 骑士精神 | 搜索状态建模，难度较高 | 冲刺 |
链接：
https://www.luogu.com.cn/problem/P1135
https://www.luogu.com.cn/problem/P1746
https://www.luogu.com.cn/problem/P1126
https://www.luogu.com.cn/problem/P1379
https://www.luogu.com.cn/problem/P2324
说明：P2324 难度明显高于深圳自招基础要求，适合强学生拓展。
十三、本阶段作业
- 对 P1135 写出完整建模说明。
- 完成 P1135。
- 设计一道“数字变换”题，并写出状态和转移。
- 选做 P1126，重点不是 AC，而是理解为什么状态要包含方向。
十四、本阶段小结
状态图 BFS 是自招建模的重点。
口诀：
状态当作点，操作当作边。
每步代价一，BFS 求最短。
信息不够用，状态加一维。
这里空空如也
有帮助，赞一个