0752. Open the Lock¶
题目信息¶
- 题号:
0752
- 难度:
Medium
- 主题:
状态空间、最少操作次数、字符串
- 原题:
- 重点:
锁从
0000开始,每次仅将一个转轮拨动一格且数字首尾相接;死锁状态一旦显示便不能继续操作,需要返回到达目标的最少拨动次数或-1
题目重述¶
一个四位密码锁由四个独立转轮组成,每个转轮依次包含数字 0 至 9,并允许 9 与 0 之间首尾相接。锁的初始显示为 "0000"。一次操作只能选择一个转轮,将其向前或向后拨动一格。
给定一组四位字符串 deadends 和目标字符串 target。当锁显示为任一 deadends 中的状态时,转轮会立即锁死,之后无法再进行操作。请返回从初始状态到达 target 所需的最少操作次数;若无法在避开死锁状态的前提下到达目标,返回 -1。若初始状态本身是死锁状态,也无法开始操作。
deadends 的长度在 [1, 500] 范围内;每个死锁状态和 target 都恰好由四个数字字符组成,并且 target 不在 deadends 中。
自建示例¶
两个不同转轮各拨动一次:
输入:deadends = ["0001","0100","2222"], target = "1010"
输出:2
解释:可以先把第一个转轮从 0 拨到 1,得到 "1000";再把第三个转轮从 0 拨到 1,得到 "1010"。这条路径不经过任何死锁状态。目标有两个位置不同于初始状态,而一次操作只能改变一个位置,所以少于两次不可能到达。
初始状态已经锁死:
输入:deadends = ["0000","5555"], target = "1234"
输出:-1
解释:锁一开始就显示死锁状态 "0000",无法进行任何拨动。