# LeetCode: 752. 打开转盘锁¶

## 1、题目描述¶

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



输入: deadends = ["8888"], target = "0009"



输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"



输入: deadends = ["0000"], target = "8888"



• 死亡列表 deadends 的长度范围为 [1, 500]
• 目标数字 target 不会在 deadends 之中。
• 每个 deadendstarget 中的字符串的数字会在 10,000 个可能的情况 '0000''9999' 中产生。

## 2、解题思路¶

• BFS 广度优先搜索

• 每个状态都有8个状态可选，设置一个记录访问过的集合

class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
return -1

appear = {"0000", }

def next_status(stat):
temp = list(stat)
for i in range(4):
yield "".join(temp[:i] + [str((int(temp[i]) + 9) % 10)] + temp[i + 1:])
yield "".join(temp[:i] + [str((int(temp[i]) + 11) % 10)] + temp[i + 1:])

ans = -1
cur = ["0000"]
step = 0
find = False
while not find and cur:
temp_next = []
for n in cur:
if n == target:
ans = step
find = True
break
if not find:
for nex in next_status(n):
if nex not in dead_set and nex not in appear: