0752. 打开转盘锁【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - BFS

1. 📝 题目描述

• leetcode

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

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

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

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

---

示例 1：

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

示例 2：

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

示例 3：

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

---

提示：

• 1 <= deadends.length <= 500
• deadends[i].length == 4
• target.length == 4
• target 不在 deadends 之中
• target 和 deadends[i] 仅由若干位数字组成

2. 🎯 s.1 - BFS

c

int openLock(char** deadends, int deadendsSize, char* target) {
    int dead[10000];
    memset(dead, 0, sizeof(dead));
    for (int i = 0; i < deadendsSize; i++) {
        dead[atoi(deadends[i])] = 1;
    }
    if (dead[0]) return -1;
    int t = atoi(target);
    int visited[10000];
    memset(visited, 0, sizeof(visited));
    visited[0] = 1;
    int queue[10000], head = 0, tail = 0;
    queue[tail++] = 0;
    int step = 0;
    while (head < tail) {
        int size = tail - head;
        for (int i = 0; i < size; i++) {
            int cur = queue[head++];
            if (cur == t) return step;
            int digits[4] = {cur/1000, cur/100%10, cur/10%10, cur%10};
            for (int j = 0; j < 4; j++) {
                for (int d = -1; d <= 1; d += 2) {
                    int old = digits[j];
                    digits[j] = (old + d + 10) % 10;
                    int next = digits[0]*1000 + digits[1]*100 + digits[2]*10 + digits[3];
                    if (!visited[next] && !dead[next]) {
                        visited[next] = 1;
                        queue[tail++] = next;
                    }
                    digits[j] = old;
                }
            }
        }
        step++;
    }
    return -1;
}

js

/**
 * @param {string[]} deadends
 * @param {string} target
 * @return {number}
 */
var openLock = function (deadends, target) {
  const dead = new Set(deadends)
  if (dead.has('0000')) return -1
  const visited = new Set(['0000'])
  const queue = ['0000']
  let step = 0
  while (queue.length) {
    const size = queue.length
    for (let i = 0; i < size; i++) {
      const cur = queue.shift()
      if (cur === target) return step
      for (let j = 0; j < 4; j++) {
        for (const d of [-1, 1]) {
          const arr = cur.split('')
          arr[j] = '' + ((+arr[j] + d + 10) % 10)
          const next = arr.join('')
          if (!visited.has(next) && !dead.has(next)) {
            visited.add(next)
            queue.push(next)
          }
        }
      }
    }
    step++
  }
  return -1
}

py

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        dead = set(deadends)
        if '0000' in dead:
            return -1
        visited = {'0000'}
        queue = deque(['0000'])
        step = 0
        while queue:
            for _ in range(len(queue)):
                cur = queue.popleft()
                if cur == target:
                    return step
                for j in range(4):
                    for d in (-1, 1):
                        nxt = cur[:j] + str((int(cur[j]) + d) % 10) + cur[j+1:]
                        if nxt not in visited and nxt not in dead:
                            visited.add(nxt)
                            queue.append(nxt)
            step += 1
        return -1

• 时间复杂度：$O({10}^4\times 4)$，最多遍历 10000 个状态
• 空间复杂度：$O({10}^4)$

算法思路：

• 将每个 4 位密码视为图中的节点，相邻节点是拨动一位后的状态
• 介 0000 开始 BFS，跳过死亡数字，返回到达 target 的最少步数