难度：★★★☆☆
类型：图
方法：宽度优先搜索
力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。
示例 1:
输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出：6
解释：
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，
因为当拨动到 "0102" 时这个锁就会被锁定。
示例 2:
输入: deadends = ["8888"], target = "0009"
输出：1
解释：
把最后一位反向旋转一次即可 "0000" -> "0009"。
示例 3:
输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
输出：-1
解释：
无法旋转到目标数字且不被锁定。
示例 4:
输入: deadends = ["0000"], target = "8888"
输出：-1
提示：
死亡列表 deadends 的长度范围为 [1, 500]。
目标数字 target 不会在 deadends 之中。
每个 deadends 和 target 中的字符串的数字会在 10,000 个可能的情况 '0000' 到 '9999' 中产生。
四位数的密码其实可以看做一个空间，从0000到9999一共有10的四次方种可能性。我们把这一万种可能性看成图中的一万个结点，图是无向的，这些结点之间在图上存在着某种位置关系，即通过把旋钮旋转一位可以得到相邻的状态，或者相邻的结点，而且有规则的是，所有结点都和8个结点相邻，例如，0000点的相邻点为9000，0900，0090，0009，1000，0100，0010和0001。
我们使用图的宽度优先搜索的方法来解决这个问题。我们需要准备两个变量：
定义一个队列queue，用来表达即将需要研究的结点列表，列表中每个元素是一个元素，表达当前结点node及到达当前结点已经使用的步数step；
定义一个集合seen，用来表达已经被研究过的点的集合，从而避免重复研究导致的计算爆炸。
有了这两个变量，就可以开始宽度优先搜索的流程：
1. 循环遍历，每次从队列中弹出一个结点对其展开研究；
2. 特殊的处理，如果该结点即为最终目标节点（密码），则直接返回该结点对应步数；如果该结点是死亡结点，则跳出本次循环，继续下一个结点；
3. 该节点是普通结点，针对其8个相邻结点展开研究：如果该相邻结点在seen集合中见过了，则直接跳过，否则将该结点加入队列尾，准备研究。
最后循环结束后，如果队列空空仍无法到达目标结点，说明目标结点被死亡结点直接或间接包围了，直接返回-1。
如有疑问或建议，欢迎评论区留言~
有关更多力扣中等题的python解决方案，请移步力扣中等题解析
网友评论