发表于 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

• LC 题目链接