LeetCode 752. 打开转盘锁
目录
题目描述
题意分析
四个拨轮各有
0到9十个刻度且首尾相连，初始状态是0000，每一次操作只能把某一位向上或向下拨一格；给定一批deadends（死亡数字），锁一旦转到其中任意一个就再也拨不动了，问最少拨多少次能到达target，到不了返回-1。把每个四位字符串看成一个节点，一次拨动看成连接两个节点的一条边，那么每条边的代价都是 1——这是一个无权图上的最短路问题，而不是需要按代价排序的加权最短路。所有拨法从
0000出发一层层扩散，第一次碰到target时经过的层数就是答案。死亡数字是这张图上被挖掉的点：它们既不能作为终点，也不能作为中转，扩展时必须整个跳过。特别地，起点
0000本身也可能出现在deadends里，此时一步都拨不了，必须直接返回-1。约束信号：状态总数固定是 $10^4$，
deadends长度上限五百，规模极小，说明朴素的逐层扩散就足够，不需要任何启发式；同时也提示要用集合去重，否则状态会被反复访问。边界包括：起点在死亡列表中；
target就是0000（答案为 0）；target被死亡数字完全包围而不可达；拨轮的环形跨越，即9向上变0、0向下变9。
解法：BFS 按层扩展状态
核心思路
把每个四位数字看成图中的一个状态。每次只能转动一个拨轮一格，所以每个状态最多有 8 个相邻状态；每条边的代价都是 1，问题就是从
0000到target的无权图最短路。BFS 按距离逐层扩展：第
step层中的状态都恰好距离起点step次操作，因此第一次取出target时，step就是最少操作数。DFS 只能找到一条路径，不能保证第一次命中的是最短路径。
deadends是从状态图中删除的节点：既不能进入，也不能从中继续扩展。起点0000不经过邻居过滤，所以若它本身是死亡状态，必须在 BFS 前直接返回-1。层序 BFS 的不变量是：每轮开始时，队列当前的
size个元素都位于同一距离层；所有已入队状态都已经标记为访问。固定size能避免下一层混入本层，入队时标记则能避免同一状态被多条路径重复加入。
解题步骤
- 将所有死亡状态加入哈希集合，先检查
0000是否被封锁。- 将
0000入队并立即加入访问集合，令step = 0。- 每轮记录当前队列长度
size，只处理这size个同层状态。- 出队状态若等于
target，立即返回step。- 对四个拨轮分别生成向上、向下转一格的 8 个邻居；
9向上回到0，0向下回到9。- 跳过死亡或已访问状态，其余状态在入队时立刻标记。
- 当前层处理完后执行
step++；队列耗尽仍未命中则返回-1。例如从
0000到0009，第四位向下转一次即可到达，BFS 会在第 1 层命中。若0009在死亡集合中，它不会被加入队列，搜索最终返回-1。
代码实现
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Queue;
import java.util.Set;
class Solution {
public int openLock(String[] deadends, String target) {
Set<String> dead = new HashSet<>();
for (String state : deadends) {
dead.add(state);
}
if (dead.contains("0000")) {
return -1;
}
Queue<String> queue = new ArrayDeque<>();
Set<String> visited = new HashSet<>();
queue.offer("0000");
visited.add("0000");
int step = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
String current = queue.poll();
if (current.equals(target)) {
return step;
}
for (String next : nextStates(current)) {
if (dead.contains(next) || !visited.add(next)) {
continue;
}
queue.offer(next);
}
}
step++;
}
return -1;
}
private List<String> nextStates(String state) {
List<String> next = new ArrayList<>(8);
char[] digits = state.toCharArray();
for (int i = 0; i < 4; i++) {
char original = digits[i];
digits[i] = original == '9' ? '0' : (char) (original + 1);
next.add(new String(digits));
digits[i] = original == '0' ? '9' : (char) (original - 1);
next.add(new String(digits));
digits[i] = original;
}
return next;
}
}
func openLock(deadends []string, target string) int {
dead := make(map[string]bool, len(deadends))
for _, state := range deadends {
dead[state] = true
}
if dead["0000"] {
return -1
}
queue := []string{"0000"}
visited := map[string]bool{"0000": true}
step := 0
for len(queue) > 0 {
size := len(queue)
for i := 0; i < size; i++ {
current := queue[0]
queue = queue[1:]
if current == target {
return step
}
for _, next := range nextLockStates(current) {
if dead[next] || visited[next] {
continue
}
visited[next] = true
queue = append(queue, next)
}
}
step++
}
return -1
}
func nextLockStates(state string) []string {
next := make([]string, 0, 8)
digits := []byte(state)
for i := 0; i < 4; i++ {
original := digits[i]
if original == '9' {
digits[i] = '0'
} else {
digits[i] = original + 1
}
next = append(next, string(digits))
if original == '0' {
digits[i] = '9'
} else {
digits[i] = original - 1
}
next = append(next, string(digits))
digits[i] = original
}
return next
}
复杂度分析
设状态图中最多有
V = 10000个状态，每个状态最多连接 8 个邻居。
- 时间复杂度：$O(V)$。每个可达状态最多入队一次，生成邻居的数量和字符串长度都是常数。
- 空间复杂度：$O(V)$。队列、访问集合和死亡集合最多共同保存常数倍的全部状态。
关键点总结
- 边权全部为 1，BFS 的层数天然就是最少拨动次数。
- 死亡状态不能入队；起点是死亡状态必须单独特判。
visited要在入队时标记，而不是出队时标记，才能避免同层重复入队。- 每层先固定
size，处理结束后再增加step，否则距离会与出队次数混淆。- 生成某一位的两个邻居后要恢复原字符，才能继续正确修改下一位。
- 面试若追问优化，可说明双向 BFS 从起点和终点同时扩展，并始终扩展较小的一侧；但状态只有一万个，单向 BFS 已足够稳定。
易错点总结
- 起点
0000在deadends中仍启动搜索，会从一个本应不可移动的状态走出去。- 忘记过滤死亡状态，会让最短路径非法穿过禁区。
- 出队时才标记访问，同一状态可能在同一层被多次入队，导致队列快速膨胀。
- 把
step++放在单个状态的循环里，计算出的会是出队次数而不是最短距离。- 没处理拨轮环形边界：
0向下应为9，9向上应为0。- 修改一位后没有恢复原字符，会生成同时改变多位的非法邻居。
- 只在生成邻居时判断目标，会漏掉
target = "0000"的零步答案；出队时判断可自然覆盖。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 127. 单词接龙 | 困难 | 字符串状态图建边 |
| 433. 最小基因变化 | 中等 | 有限字符集逐位替换 |
| 773. 滑动谜题 | 困难 | 棋盘状态编码与还原 |
| 994. 腐烂的橘子 | 中等 | 多源 BFS 计层数 |
| 1091. 二进制矩阵中的最短路径 | 中等 | 网格八方向最短路 |
| 1129. 颜色交替的最短路径 | 中等 | 带附加维度的状态最短路 |
| 1345. 跳跃游戏 IV | 困难 | 建图去重压缩边数 |