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