752. 打开转盘锁

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

解法一：bfs

起点是字符串"0000"，终点是target，求"0000"变为target的最少操作次数，即bfs问题

import queue
class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        q = queue.Queue()   #队列
        q.put('0000')   #初始放入起点
        visited = set()  #记录访问过的结点
        deadendsSet = set(deadends)     #deadends转为集合加快查询
        step = 0  #旋转次数
        visited.add("0000")   #标记起点已访问
        
        #辅助函数
        #将s[j]位加1
        def plusOne(s, j):
            chs = list(s)
            if chs[j] == '9':
                chs[j] = '0'
            else:
                chs[j] = str(int(chs[j])+1)
            return ''.join(chs)
        #将s[j]位减1
        def minusOne(s, j):
            chs = list(s)
            if chs[j] == '0':
                chs[j] = '9'
            else:
                chs[j] = str(int(chs[j])-1)
            return ''.join(chs)
        
        
        while not q.empty():
            #记录当前队列大小（BFS本轮迭代），以供后续遍历
            size = q.qsize()
            for i in range(size):                
                cur = q.get()  #从队列取出一个
                if cur in deadendsSet:
                    continue
                if cur == target:
                    return step
                for j in range(4):
                    #cur[j]加一，结果放入队列
                    p = plusOne(cur, j)
                    if p not in visited:
                        q.put(p)
                        visited.add(p)
                    #cur[j]减一，结果放入队列
                    m = minusOne(cur, j)
                    if m not in visited:
                        q.put(m)
                        visited.add(m)
            step += 1
        return -1