题目链接

https://leetcode.com/problems/open-the-lock

题目描述

给你一个带有4个圆形拨轮的转盘锁。每个拨轮有10个数字：'0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以*旋转：例如把 '9' 变为  '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。锁的初始数字为 '0000' ，一个代表四个拨轮数字的字符串。

列表 deadends 包含了一组死亡数字，一旦拨轮数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。

示例

输入：deadends = ["0201","0101","0102","1212","2002"],target = "0202"

输出：6

可能的移动序列为："0000"->"1000"->"1100"->"1200"->"1201"->"1202"->"0202"

需要注意的是"0000"->"0001"->"0002"->"0102"->"0202"这样的序列是不能被解锁的，因为拨动到"0102"时锁会被锁定。

解题思路

由于有4把锁，即一共有4个位置，每个位置可以向上转也可以向下转，因此每转动一次有八种可能。因此这个问题可以抽象成一个图，每个节点有8个相邻节点，求"0000"到目标节点target的最短距离。因此这道题可以用BFS来做。

但是需要在BFS模板的基础上增加对deadends的处理，如果有节点在deadends内，就需要跳过这个节点。因为这个节点是不能出现在路径中的。同时在这道题中要维护好visited集合，避免走回头路。

在代码实现时， 抽象出函数moveUp(s,i)和moveDown(s,i)，分别表示将s[i]向上拨动一次和向下拨动一次的结果。

注意在Python中，字符串是不可变类型，即无法直接修改字符串的某一位字符。因此我们采取先将字符串转为list，然后再用join将list中的元素拼成字符串。

代码实现

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        #s[i]向上拨动后得到的新字符串
        def moveUp(s,i):
            s = list(s)#字符串是不可变类型，无法直接修改字符串中的某个字符，因此我们先转为列表修改某个字符后，再转为字符串
            if s[i] == '0': #0往上拨就是9
                s[i] = '9' 
            else:
                s[i] = str(int(s[i])-1)
            return ''.join(s)
        #s[i]向下拨动后得到的新字符串
        def moveDown(s,i):
            s = list(s)
            if s[i] == '9': #9往下拨就是0
                s[i] = '0'
            else:
                s[i] = str(int(s[i])+1)
            return ''.join(s)
        
        queue = ['0000'] #BFS所用队列，先将起始点加入
        visited = set('0000') #存储已经访问过的节点
        step = 0
        while queue:#队列不为空的情况下进行循环
            #先把这一层遍历完，因此找queue的大小
            n = len(queue)
            for num in range(n):
                cur = queue.pop(0) #弹出队首元素并判断
                if (cur == target):
                    return step
                if (cur in deadends): #判断当前节点是否在deadends中
                    continue
                #将相邻的8个”节点”加入队列
                for i in range(4):
                    tmp_up = moveUp(cur,i)
                    if tmp_up not in visited: #一定要注意这里要有判断
                        #加入队列
                        queue.append(tmp_up)
                        #改变访问状态
                        visited.add(tmp_up)
                    tmp_down = moveDown(cur,i)
                    if tmp_down not in visited:
                        #加入队列
                        queue.append(tmp_down)
                        # 改变访问状态
                        visited.add(tmp_down)
            step += 1 #这一层遍历完了之后增加步数    
        return -1 #等queue为空时遍历结束，如果没有找到target就要返回-1



        
        
        
        
        

参考

https://labuladong.gitbook.io/algo/suan-fa-si-wei-xi-lie/bfs-suan-fa/bfs-kuang-jia

https://www.jb51.net/article/150063.htm