JZX轻语：简
LeetCode 752 - 打开转盘锁
发表于2024年04月29日
BFS的应用，使用BFS模拟可能的所有转法(从第1位开始，往上拨or往下拨，直至第4位)。如果某个转法已经处理过or锁死，则不加入队列中。
from collections import deque
class Solution:
def _roll(self, cur_lock: str):
for i in range(4):
yield cur_lock[:i] + (chr(ord(cur_lock[i]) + 1) if cur_lock[i] != '9' else '0') + cur_lock[(i + 1):]
yield cur_lock[:i] + (chr(ord(cur_lock[i]) - 1) if cur_lock[i] != '0' else '9') + cur_lock[(i + 1):]
def openLock(self, deadends: List[str], target: str) -> int:
q = deque()
visited = set()
deadends = set(deadends)
if '0000' in deadends:
return -1
q.append((0, '0000'))
while q:
step, cur = q.popleft()
if cur == target:
return step
for next_ in self._roll(cur):
if next_ in visited or next_ in deadends:
continue
visited.add(next_)
q.append((step + 1, next_))
return -1