题目

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把’9’变成’0’，’0’变成’9’。每个旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为’0000’，一个代表四个拨轮的数字的字符串。

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

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

思路

问题本质：从一幅图中找到从起点到终点的最短距离。
参考解析：
https://leetcode-cn.com/problems/open-the-lock/solution/wo-xie-liao-yi-tao-bfs-suan-fa-kuang-jia-jian-dao-/

熟练掌握BFS算法框架

  1. class Solution:
  2.     def openLock(self, deadends: List[str], target: str) -> int:
  3.         queue = ['0000'] # 起点'0000'加入队列
  4.         marked = set('0000') # 避免走回头路
  5.         step = 0 # 记录扩散的步数
  7.         while len(queue) != 0:
  8.             size = len(queue)
  9.             for _ in range(size):
  10.                 # 当前队列中的节点向四周扩散
  11.                 curPassWD = queue.pop(0)
  12.                 if curPassWD == target:
  13.                     return step
  14.                 if curPassWD in deadends:
  15.                     continue
  17.                 # 当前密码旋转一次，有八种可能
  18.                 for i in range(4):
  19.                     for j in (-1, 1):
  20.                         # 向后、向前拨动
  21.                         curPassWDCopy = curPassWD[:i] + str((int(curPassWD[i]) + j) % 10) + curPassWD[i+1:]
  22.                         # 避免走回头路
  23.                         if curPassWDCopy not in marked:
  24.                             queue.append(curPassWDCopy)
  25.                             marked.add(curPassWDCopy)
  27.             step += 1
  29.         return -1