题目描述
思路解析动画文字版
换个眼光:每个密码是地图上的一个点,能一步互拨的两个密码之间有条路。于是「最少拨几下」=「图上从 0000 到 0202 最短走几步」。
为什么不乱走或 DFS?乱走会绕远,DFS 一头扎到底找到的也未必最短。BFS 严格按层扩,第一次扩到目标的圈数就是答案。
下面开始一帧一帧演 BFS:盯住当前扩展的状态、它生成的8 个邻居、谁被 dead/visited 筛掉、队列怎么长、层数(步数)怎么涨。
第 0 层 · 起点入队：起跑线:把 0000 入队,标进 visited,记它是第 0 层(拨 0 下就在这)。点位先空着,下面看它怎么裂出邻居。若 0000 本身就是死亡数字,直接返回 -1。
扩展 0000 · 生成 8 邻居：把 0000 出队,生成 8 个邻居:每一位分别 +1 或 −1(个位 0−1 绕回 9)。它们都不在死亡集、也没来过,全部入队并标记为第 1 层。
第 1 层 · 全部 visited：第 1 层这 8 个都进 visited 了(变深),里面没有 target(0202)。所以答案不是 1。纪律:同一层全处理完,才进下一层。
扩展 1000 · 锁定活路方向：轮到第 1 层的 1000 出队,生成它的邻居。其中 1100(百位+1)把我们带向「1 开头」,正是绕开死亡数字 0201/0101/0102 的关键岔路。回到 0000 的那格已 visited、被跳过。
第 2 层 · 新邻居记账：第 2 层这批新邻居全部记进 visited。BFS 不挑不选,谁也不漏。仍没碰到 target,继续往外扩第 3 层。1100 这格是后面活路的关键落点。
扩展 0100 · 一个被堵的方向：再扩第 1 层的 0100。它的邻居 0101 是死亡数字,直接丢弃;1100、0000 已 visited 跳过。剩下的活邻居(0200/0110/…)入第 2 层。可见每条岔路都要过一遍筛子。
为何不能走近路 0200→0202?：看似 0000→0200→0202 很近,但从 0200 拨到 0202 必经 0201(死亡数字),另一头挨着的 0102 也是死亡数字,这条近路被封死。BFS 会自动绕开,去找另一条活路——这正是 dead 集的价值。
扩展 1100 · 朝 1200 走：扩展第 2 层的 1100,生成邻居。其中 1200(百位 1→2)继续朝 0202 靠;0100 和 1000 已 visited、跳过。新邻居入第 3 层队列。
扩展 1200 · 个位起跳：扩展第 3 层的 1200,生成邻居。其中 1201(个位 0→1)是通往目标的下一跳;1100 已 visited。把新邻居纳入第 4 层。
扩展 1201 · 个位再进一格：扩展第 4 层的 1201。注意它的一个邻居 0201 是死亡数字,直接丢弃;1200 已 visited 跳过。活下来的 1202(个位 1→2)入第 5 层——离目标只差千位了。
扩展 1202 · 千位拨回 0：扩展第 5 层的 1202。把千位从 1 拨回 0,得到 0202!它不在 dead、也没 visited,入队为第 6 层。旁边的 1212 是死亡数字被丢弃,1201 已 visited。
第 6 层 · 命中 target!：0202 在第 6 层第一次被扩到——它就是 target!这一层的步数 6 就是答案。BFS 第一次碰到目标即最短,立刻收工。
完整最短路 · 第 1 跳：回放这条活路:从 0000 出发,把千位拨到 1,得到 1000(第 1 步)。一跳只动一位。
完整最短路 · 第 2 跳：接着把百位拨到 1,得到 1100(第 2 步)。这一跳把我们带向「1 开头」,正是绕开 0200 那边死亡数字的关键。
完整最短路 · 第 2 段：继续:1100 百位拨到 2 得 1200(第3步),个位拨到 1 得 1201(第4步)。路径一格格点亮,绕过了挡在 0200 那边的死亡数字。
完整最短路 · 第 5 跳：把个位从 1 拨到 2,得到 1202(第 5 步)。现在只差千位的那个 1 还没归零,离 0202 只剩最后一跳。
完整最短路 · 第 6 跳命中：最后把千位拨回 0,得到 0202(第 6 步)。整条路 0000→1000→1100→1200→1201→1202→0202 共 6 步,每跳只动一位、个个都活着——这就是 BFS 给的最优解。
按层规模全景：整体看 BFS 就是水波一圈圈往外:第 0 层 1 个、第 1 层 8 个、之后每层把所有新邻居纳入。圈数就是步数,第 6 圈第一次碰到 0202,答案锁定为 6。
易错实演 · 0 往下拨绕回 9：演示个位的环形:0000 的个位是 0,−1 不是 −1,而是绕回 9 得 0009;+1 得 0001。这就是 (x+9)%10 在干的事——转盘首尾相接。
易错实演 · 晚标 visited 的灾难：若只在出队时才标 visited,同一个 0100 会被多个邻居反复塞进队列,队列爆炸还重复扩展。正确做法:生成时就标 visited,让每个状态只进队一次。
边界三连：三个边界:目标即起点返回 0;起点是死亡数字返回 -1;目标被一圈死亡数字团团围住也返回 -1。队列空了还没碰到 target,就是到不了。
面试追问：面试常问三层:双向 BFS 提速、无障碍时的纯数学解、以及为什么这类「最少步数」题不该用 DFS。讲清这三点就稳了。
参考代码
from collections import dequedef openLock(deadends, target): dead = set(deadends) if '0000' in dead: return -1 if target == '0000': return 0 visited = {'0000'} q = deque([('0000', 0)]) while q: s, d = q.popleft() if s == target: return d for i in range(4): x = int(s[i]) for nx in ((x + 1) % 10, (x + 9) % 10): t = s[:i] + str(nx) + s[i+1:] if t not in visited and t not in dead: visited.add(t) q.append((t, d + 1)) return -1复杂度
- 时间复杂度：O(10^4·4)，最多 10000 个组合,每个生成 8 个邻居(4 位×2),常数级 → 可视作 O(N·b)
- 空间复杂度：O(10^4)，visited 和队列最多装下全部 10000 个组合
易错点
面试追问把动画讲成自己的话
追问怎么把搜索再加速一倍?
追问没有 deadends 能否不搜直接算?
追问为什么不用 DFS?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
判断二分图
LeetCode 785 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题