题目

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

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

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

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

示例 1:

  1. 输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
  2. 输出：6
  3. 解释：
  4. 可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
  5. 注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，
  6. 因为当拨动到 "0102" 时这个锁就会被锁定。

示例 2:

输入: deadends = ["8888"], target = "0009"
输出：1
解释：
把最后一位反向旋转一次即可 "0000" -> "0009"。

示例 3:

输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
输出：-1
解释：
无法旋转到目标数字且不被锁定。

示例 4:

输入: deadends = ["0000"], target = "8888"
输出：-1

提示：

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

    方案一

    ```python def get_next(num_str): return [
      str((int(num_str[0]) + 1) % 10) + num_str[1:],
  str((int(num_str[0]) - 1) % 10) + num_str[1:],
  num_str[:1] + str((int(num_str[1]) + 1) % 10) + num_str[2:],
  num_str[:1] + str((int(num_str[1]) - 1) % 10) + num_str[2:],
  num_str[:2] + str((int(num_str[2]) + 1) % 10) + num_str[3:],
  num_str[:2] + str((int(num_str[2]) - 1) % 10) + num_str[3:],
  num_str[:3] + str((int(num_str[3]) + 1) % 10),
  num_str[:3] + str((int(num_str[3]) - 1) % 10),
    ]

def openLock(deadends: [str], target: str) -> int: used = set(deadends) if “0000” in used: return -1 used.add(“0000”) deque = collections.deque([“0000”]) step = 0

while deque:
    step += 1

    for _ in range(len(deque)):
        result = deque.popleft()
        if result == target:
            return step - 1

        for next_result in get_next(result):
            if next_result not in used:
                used.add(next_result)
                deque.append(next_result)
return -1


- 直接使用bfs，未加任何优化
- leetcode 执行用时：844 ms

> 有一个解法为从 target 出发开始bfs，和，同时从起点和终点出发。

<a name="4KlW3"></a>
# 方案二
```python
def openLock(deadends: [str], target: str) -> int:
    _deadends = set(deadends)

    if '0000' in _deadends or target in _deadends:
        return -1


    def get_next_batch(runners): # 获取下一次循环的集合
        next_runners = set()
        for runner in runners:
            for i in range(4):
                next_runners.add(runner[:i] + str((int(runner[i]) - 1) % 10) + runner[i+1:])
                next_runners.add(runner[:i] + str((int(runner[i]) + 1) % 10) + runner[i+1:])
        return next_runners - _deadends

    step = 0
    start = { '0000' }

    while True:
        if not start: # 有一个集合为空则表示不能解锁
            return -1

        # 开始节点向后执行一步(开始节点转动一次)
        step += 1
        start = get_next_batch(start)
        if target in start:
            return step

        _deadends = _deadends | start
  • leetcode 执行用时：816 ms

基本思路和方案一相同，只不过这里是直接一步执行一批，终止条件为找到目标或者没有下一步。

方案三

从起点和终点同时出发，此时的结束条件变为，起点和终点生成的下一步集合中有交集。

def openLock(deadends: [str], target: str) -> int:
    _deadends = set(deadends)
    if '0000' in _deadends or target in _deadends:
        return -1
    if target == '0000':
        return 0

    def get_next_batch(runners):  # 获取下一次循环的集合
        next_runners = set()
        for runner in runners:
            for i in range(4):
                next_runners.add(
                    runner[:i] + str((int(runner[i]) - 1) % 10) + runner[i+1:])
                next_runners.add(
                    runner[:i] + str((int(runner[i]) + 1) % 10) + runner[i+1:])
        return next_runners - _deadends

    step = 0
    start = '0000'

    start_deque = collections.deque([{start}])
    end_deque = collections.deque([{target}])

    next_end = {target}
    while start_deque and end_deque:
        start = start_deque.popleft()
        next_start = get_next_batch(start)
        step += 1
        if not next_start:
            return -1
        if next_start & next_end:
            return step
        start_deque.append(next_start)

        end = end_deque.popleft()
        next_end = get_next_batch(end)
        step += 1
        if not next_end:
            return -1
        if next_start & next_end:
            return step
        end_deque.append(next_end)

交集运算会减少很多时间复杂度。

原文

https://leetcode-cn.com/explore/learn/card/queue-stack/217/queue-and-bfs/873/