752 打开转盘锁（宽搜）

小灰灰 2022-09-10 12:21 11阅读 0赞

**1. 问题描述：**

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有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

**提示：**

1 <= deadends.length <= 500  
deadends\[i\].length == 4  
target.length == 4  
target 不在 deadends 之中  
target 和 deadends\[i\] 仅由若干位数字组成  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/open-the-lock

**2. 思路分析：**

分析题目可以知道这道题目属于状态类的**宽搜**问题，已知一个初始状态，我们要求解的是从初始状态到达目标状态的最短距离，可以从一个状态到达下一个状态，所以本质上属于**无向图求解最短路径的问题**，也即典型的bfs问题。因为存在死亡状态所以一开始的时候我们需要将死亡状态加入到哈希表中（因为使用的是python语言所以可以将死亡状态加入到字典中）这样方便后面检验从上一个状态到下一个状态是否是死亡状态。bfs都是一些基本的套路，需要借助一个队列，因为使用的是python语言所以可以声明一个双端队列（collections.deque())），一开始的时候队列中加入初始状态"0000"，声明一个哈希表dist来记录已经到达过的状态的最短距离，这个哈希表其实有两个作用：第一个作用是判重，也即判断当前的状态是否出现过（这里可以避免加入之前已经访问过的状态造成死循环），第二个作用是记录到达当前状态的最短距离；只要是队列不为空那么执行循环，一开始的是弹出队首元素，然后尝试从当前状态转移到下一个状态，如果下一个状态没有出现过则更新dist，如果发现下一个状态恰好是目标状态那么直接返回对应的最短距离即可。

**3. 代码如下：**

from typing import List
    import collections
    
    
    class Solution:
        # 经典的无向图求解最短路问题: bfs
        def openLock(self, deadends: List[str], target: str) -> int:
            # start为目标状态
            start = "0000"
            if start == target: return 0
            # 将所有的死亡状态加入到字典(哈希表)中
            S = dict()
            for x in deadends:
                S[x] = 1
            # 初始状态在死亡状态中那么返回-1
            if start in S: return -1
            # 声明一个双端队列
            q = collections.deque([start])
            # 使用一个哈希表记录到达当前某个状态的最短距离
            dist = dict()
            dist[start] = 0
            while q:
                # 每一次的时候弹出元素
                t = q.popleft()
                # 尝试可能到达的状态总共有4 * 2个状态
                for i in range(4):
                    # 当前这一位可以是加1也可以减1
                    for j in range(-1, 2, 2):
                        # python中将字符串转为列表之后才可以修改
                        _t = list(t)
                        # 因为可能是加1或者减1所以有可能导致出现小于0或者大于10的情况这个时候需要 + 10之后对10取模这样保证得到的数字在[0:9]范围
                        _t[i] = str((ord(_t[i]) - ord("0") + j + 10) % 10)
                        # 将列表转为字符串
                        u = "".join(_t)
                        # 第一次搜索到的状态对应的距离一定是最短的, 当前哈希表有两个作用一个是判重一个是记录到达当前状态的最短距离
                        if u not in S and u not in dist:
                            dist[u] = dist[t] + 1
                            # 找到了目标状态
                            if u == target: return dist[u]
                            q.append(u)
            return -1