打开转盘锁

怎样从“0000→target 避开 deadends 最少拨动。”推导出 图 BFS · 转盘锁，并证明每次状态变化都不会漏掉答案？

中心结论：BFS 四位分别±1,visited 防重复;层数即步数。

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。

在本站主例中，0000→target 避开 deadends 最少拨动。

算法最终需要得到或观察：最短拨动次数。

重复从多个位置搜索会反复访问同一状态；统一的 visited 与前线结构让每个状态只处理一次。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“图搜索前线”，明确答案需要观察什么。
2. 2状态只维护 队列、visited、步数。
3. 3转移每一步按照 BFS 四位分别±1,visited 防重复;层数即步数。
4. 4收尾读取 最短拨动次数。，并复核边界与复杂度。

先把题目对象翻译成节点和边，再选择 BFS 或 DFS。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：队列、visited、步数。

此题可以转化为从起始点到终点的最短路径。采用广度优先搜索。每次广搜枚举转动一次数字的状态，并且用 visited 记录是否被搜索过，如果没有被搜索过，便加入队列，下一轮继续搜索。如果搜索到了 target，便返回对应的旋转次数。如果搜索完成后，仍没有搜索到 target，说明无法解锁，返回 -1。特殊情况，如果 target 就是初始数字 0000，那么直接返回答案 0。 在广搜之前，先将 deadends 放入 map 中，搜索中判断是否搜到了 deadends。如果初始数字 0000 出现在 deadends 中，可以直接返回答案 −1。

BFS 四位分别±1,visited 防重复;层数即步数。

执行过程中持续维护：队列、visited、步数。

正确性依赖以下不变量：状态空间 10^4,BFS 可行。

面试时可以压缩为：BFS O(10^4·4)。

落到当前题，执行机制可以压缩为：BFS 四位分别±1,visited 防重复;层数即步数。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入0000→target 避开 deadends 最少拨动。 因为：BFS 四位分别±1,visited 防重复;层数即步数。
2. 2BFS 按层扩展单词起点入队。 因为：BFS 保证最短变换序列。
3. 3扩展 '0000' 的邻词尝试每个位置的 26 字母。 因为：dict 中存在且未访问则入队。
4. 4无法到达队列空。 因为：end 不在可达集。
5. 5预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
6. 6收尾与复杂度最短拨动次数。 因为：时间 O(n) · 空间 O(1)。BFS 四位分别±1,visited 防重复;层数即步数。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

func openLock(deadends []string, target string) int {
	if target == "0000" {
		return 0
	}
	targetNum, visited := strToInt(target), make([]bool, 10000)
	visited[0] = true
	for _, deadend := range deadends {
		num := strToInt(deadend)
		if num == 0 {
			return -1
		}
		visited[num] = true
	}
	depth, curDepth, nextDepth := 0, []int16{0}, make([]int16, 0)
	var nextNum int16
	for len(curDepth) > 0 {
		nextDepth = nextDepth[0:0]
		for _, curNum := range curDepth {
			for incrementer := int16(1000); incrementer > 0; incrementer /= 10 {
				digit := (curNum / incrementer) % 10
				if digit == 9 {
					nextNum = curNum - 9*incrementer
				} else {
					nextNum = curNum + incrementer
				}
				if nextNum == targetNum {
					return depth + 1
				}
				if !visited[nextNum] {
					visited[nextNum] = true
					nextDepth = append(nextDepth, nextNum)
				}
				if digit == 0 {
					nextNum = curNum + 9*incrementer
				} else {
					nextNum = curNum - incrementer
				}
				if nextNum == targetNum {
					return depth + 1
				}
				if !visited[nextNum] {
					visited[nextNum] = true
					nextDepth = append(nextDepth, nextNum)
				}
			}
		}
		curDepth, nextDepth = nextDepth, curDepth
		depth++
	}
	return -1
}

func strToInt(str string) int16 {
	return int16(str[0]-'0')*1000 + int16(str[1]-'0')*100 + int16(str[2]-'0')*10 + int16(str[3]-'0')
}

func main() {
    // 1. 主例
    //    输入：mode="word-ladder", beginWord="0000", endWord="0202", wordList=["0101","0102","0103","0202"]
    //    期望：最短拨动次数。
    //
    // 2. 失败 / 未命中
    //    检查：deadends 用 set。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC127 单词接龙；LC1091 矩阵
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意0000→target 避开 deadends 最少拨动。
2. 2重复重复从多个位置搜索会反复访问同一状态；统一的 visited 与前线结构让每个状态只处理一次。
3. 3优化BFS 四位分别±1,visited 防重复;层数即步数。
4. 4证明状态空间 10^4,BFS 可行。
5. 5复杂度时间 O(n)，空间 O(1)