Question

752. 打开转盘锁

English Version

题目描述

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有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] 仅由若干位数字组成

解法

方法一：朴素 BFS

直接用朴素 BFS。

class Solution:
  def openLock(self, deadends: List[str], target: str) -> int:
    def next(s):
      res = []
      s = list(s)
      for i in range(4):
        c = s[i]
        s[i] = '9' if c == '0' else str(int(c) - 1)
        res.append(''.join(s))
        s[i] = '0' if c == '9' else str(int(c) + 1)
        res.append(''.join(s))
        s[i] = c
      return res

    if target == '0000':
      return 0
    s = set(deadends)
    if '0000' in s:
      return -1
    q = deque([('0000')])
    s.add('0000')
    ans = 0
    while q:
      ans += 1
      for _ in range(len(q)):
        p = q.popleft()
        for t in next(p):
          if t == target:
            return ans
          if t not in s:
            q.append(t)
            s.add(t)
    return -1

class Solution {
  public int openLock(String[] deadends, String target) {
    if ("0000".equals(target)) {
      return 0;
    }
    Set<String> s = new HashSet<>(Arrays.asList(deadends));
    if (s.contains("0000")) {
      return -1;
    }
    Deque<String> q = new ArrayDeque<>();
    q.offer("0000");
    s.add("0000");
    int ans = 0;
    while (!q.isEmpty()) {
      ++ans;
      for (int n = q.size(); n > 0; --n) {
        String p = q.poll();
        for (String t : next(p)) {
          if (target.equals(t)) {
            return ans;
          }
          if (!s.contains(t)) {
            q.offer(t);
            s.add(t);
          }
        }
      }
    }
    return -1;
  }

  private List<String> next(String t) {
    List res = new ArrayList<>();
    char[] chars = t.toCharArray();
    for (int i = 0; i < 4; ++i) {
      char c = chars[i];
      chars[i] = c == '0' ? '9' : (char) (c - 1);
      res.add(String.valueOf(chars));
      chars[i] = c == '9' ? '0' : (char) (c + 1);
      res.add(String.valueOf(chars));
      chars[i] = c;
    }
    return res;
  }
}

class Solution {
public:
  int openLock(vector<string>& deadends, string target) {
    unordered_set<string> s(deadends.begin(), deadends.end());
    if (s.count("0000")) return -1;
    if (target == "0000") return 0;
    queue<string> q{{"0000"}};
    s.insert("0000");
    int ans = 0;
    while (!q.empty()) {
      ++ans;
      for (int n = q.size(); n > 0; --n) {
        string p = q.front();
        q.pop();
        for (string t : next(p)) {
          if (target == t) return ans;
          if (!s.count(t)) {
            q.push(t);
            s.insert(t);
          }
        }
      }
    }
    return -1;
  }

  vector<string> next(string& t) {
    vector<string> res;
    for (int i = 0; i < 4; ++i) {
      char c = t[i];
      t[i] = c == '0' ? '9' : (char) (c - 1);
      res.push_back(t);
      t[i] = c == '9' ? '0' : (char) (c + 1);
      res.push_back(t);
      t[i] = c;
    }
    return res;
  }
};

func openLock(deadends []string, target string) int {
  if target == "0000" {
    return 0
  }
  s := make(map[string]bool)
  for _, d := range deadends {
    s[d] = true
  }
  if s["0000"] {
    return -1
  }
  q := []string{"0000"}
  s["0000"] = true
  ans := 0
  next := func(t string) []string {
    s := []byte(t)
    var res []string
    for i, b := range s {
      s[i] = b - 1
      if s[i] < '0' {
        s[i] = '9'
      }
      res = append(res, string(s))
      s[i] = b + 1
      if s[i] > '9' {
        s[i] = '0'
      }
      res = append(res, string(s))
      s[i] = b
    }
    return res
  }
  for len(q) > 0 {
    ans++
    for n := len(q); n > 0; n-- {
      p := q[0]
      q = q[1:]
      for _, t := range next(p) {
        if target == t {
          return ans
        }
        if !s[t] {
          q = append(q, t)
          s[t] = true
        }
      }
    }
  }
  return -1
}

方法二：双向 BFS

本题也可以用双向 BFS 优化搜索空间，从而提升效率。

双向 BFS 是 BFS 常见的一个优化方法，主要实现思路如下：

1. 创建两个队列 q1, q2 分别用于“起点 -> 终点”、“终点 -> 起点”两个方向的搜索；
2. 创建两个哈希表 m1, m2 分别记录访问过的节点以及对应的扩展次数（步数）；
3. 每次搜索时，优先选择元素数量较少的队列进行搜索扩展，如果在扩展过程中，搜索到另一个方向已经访问过的节点，说明找到了最短路径；
4. 只要其中一个队列为空，说明当前方向的搜索已经进行不下去了，说明起点到终点不连通，无需继续搜索。

while q1 and q2:
  if len(q1) <= len(q2):
    # 优先选择较少元素的队列进行扩展
    extend(m1, m2, q1)
  else:
    extend(m2, m1, q2)


def extend(m1, m2, q):
  # 新一轮扩展
  for _ in range(len(q)):
    p = q.popleft()
    step = m1[p]
    for t in next(p):
      if t in m1:
        # 此前已经访问过
        continue
      if t in m2:
        # 另一个方向已经搜索过，说明找到了一条最短的连通路径
        return step + 1 + m2[t]
      q.append(t)
      m1[t] = step + 1

class Solution:
  def openLock(self, deadends: List[str], target: str) -> int:
    def next(s):
      res = []
      s = list(s)
      for i in range(4):
        c = s[i]
        s[i] = '9' if c == '0' else str(int(c) - 1)
        res.append(''.join(s))
        s[i] = '0' if c == '9' else str(int(c) + 1)
        res.append(''.join(s))
        s[i] = c
      return res

    def extend(m1, m2, q):
      for _ in range(len(q)):
        p = q.popleft()
        step = m1[p]
        for t in next(p):
          if t in s or t in m1:
            continue
          if t in m2:
            return step + 1 + m2[t]
          m1[t] = step + 1
          q.append(t)
      return -1

    def bfs():
      m1, m2 = {"0000": 0}, {target: 0}
      q1, q2 = deque([('0000')]), deque([(target)])
      while q1 and q2:
        t = extend(m1, m2, q1) if len(q1) <= len(q2) else extend(m2, m1, q2)
        if t != -1:
          return t
      return -1

    if target == '0000':
      return 0
    s = set(deadends)
    if '0000' in s:
      return -1
    return bfs()

class Solution {
  private String start;
  private String target;
  private Set<String> s = new HashSet<>();

  public int openLock(String[] deadends, String target) {
    if ("0000".equals(target)) {
      return 0;
    }
    start = "0000";
    this.target = target;
    for (String d : deadends) {
      s.add(d);
    }
    if (s.contains(start)) {
      return -1;
    }
    return bfs();
  }

  private int bfs() {
    Map<String, Integer> m1 = new HashMap<>();
    Map<String, Integer> m2 = new HashMap<>();
    Deque<String> q1 = new ArrayDeque<>();
    Deque<String> q2 = new ArrayDeque<>();
    m1.put(start, 0);
    m2.put(target, 0);
    q1.offer(start);
    q2.offer(target);
    while (!q1.isEmpty() && !q2.isEmpty()) {
      int t = q1.size() <= q2.size() ? extend(m1, m2, q1) : extend(m2, m1, q2);
      if (t != -1) {
        return t;
      }
    }
    return -1;
  }

  private int extend(Map<String, Integer> m1, Map<String, Integer> m2, Deque<String> q) {
    for (int n = q.size(); n > 0; --n) {
      String p = q.poll();
      int step = m1.get(p);
      for (String t : next(p)) {
        if (m1.containsKey(t) || s.contains(t)) {
          continue;
        }
        if (m2.containsKey(t)) {
          return step + 1 + m2.get(t);
        }
        m1.put(t, step + 1);
        q.offer(t);
      }
    }
    return -1;
  }

  private List<String> next(String t) {
    List res = new ArrayList<>();
    char[] chars = t.toCharArray();
    for (int i = 0; i < 4; ++i) {
      char c = chars[i];
      chars[i] = c == '0' ? '9' : (char) (c - 1);
      res.add(String.valueOf(chars));
      chars[i] = c == '9' ? '0' : (char) (c + 1);
      res.add(String.valueOf(chars));
      chars[i] = c;
    }
    return res;
  }
}

class Solution {
public:
  unordered_set<string> s;
  string start;
  string target;

  int openLock(vector<string>& deadends, string target) {
    if (target == "0000") return 0;
    for (auto d : deadends) s.insert(d);
    if (s.count("0000")) return -1;
    this->start = "0000";
    this->target = target;
    return bfs();
  }

  int bfs() {
    unordered_map<string, int> m1;
    unordered_map<string, int> m2;
    m1[start] = 0;
    m2[target] = 0;
    queue<string> q1{{start}};
    queue<string> q2{{target}};
    while (!q1.empty() && !q2.empty()) {
      int t = q1.size() <= q2.size() ? extend(m1, m2, q1) : extend(m2, m1, q2);
      if (t != -1) return t;
    }
    return -1;
  }

  int extend(unordered_map<string, int>& m1, unordered_map<string, int>& m2, queue<string>& q) {
    for (int n = q.size(); n > 0; --n) {
      string p = q.front();
      int step = m1[p];
      q.pop();
      for (string t : next(p)) {
        if (s.count(t) || m1.count(t)) continue;
        if (m2.count(t)) return step + 1 + m2[t];
        m1[t] = step + 1;
        q.push(t);
      }
    }
    return -1;
  }

  vector<string> next(string& t) {
    vector<string> res;
    for (int i = 0; i < 4; ++i) {
      char c = t[i];
      t[i] = c == '0' ? '9' : (char) (c - 1);
      res.push_back(t);
      t[i] = c == '9' ? '0' : (char) (c + 1);
      res.push_back(t);
      t[i] = c;
    }
    return res;
  }
};

func openLock(deadends []string, target string) int {
  if target == "0000" {
    return 0
  }
  s := make(map[string]bool)
  for _, d := range deadends {
    s[d] = true
  }
  if s["0000"] {
    return -1
  }
  next := func(t string) []string {
    s := []byte(t)
    var res []string
    for i, b := range s {
      s[i] = b - 1
      if s[i] < '0' {
        s[i] = '9'
      }
      res = append(res, string(s))
      s[i] = b + 1
      if s[i] > '9' {
        s[i] = '0'
      }
      res = append(res, string(s))
      s[i] = b
    }
    return res
  }

  extend := func(m1, m2 map[string]int, q *[]string) int {
    for n := len(*q); n > 0; n-- {
      p := (*q)[0]
      *q = (*q)[1:]
      step, _ := m1[p]
      for _, t := range next(p) {
        if s[t] {
          continue
        }
        if _, ok := m1[t]; ok {
          continue
        }
        if v, ok := m2[t]; ok {
          return step + 1 + v
        }
        m1[t] = step + 1
        *q = append(*q, t)
      }
    }
    return -1
  }

  bfs := func() int {
    q1 := []string{"0000"}
    q2 := []string{target}
    m1 := map[string]int{"0000": 0}
    m2 := map[string]int{target: 0}
    for len(q1) > 0 && len(q2) > 0 {
      t := -1
      if len(q1) <= len(q2) {
        t = extend(m1, m2, &q1)
      } else {
        t = extend(m2, m1, &q2)
      }
      if t != -1 {
        return t
      }
    }
    return -1
  }

  return bfs()
}

方法三：A*算法

A* 算法主要思想如下：

1. 将 BFS 队列转换为优先队列（小根堆）；
2. 队列中的每个元素为 (dist[state] + f(state), state)，dist[state] 表示从起点到当前 state 的距离，f(state) 表示从当前 state 到终点的估计距离，这两个距离之和作为堆排序的依据；
3. 当终点第一次出队时，说明找到了从起点到终点的最短路径，直接返回对应的 step；
4. f(state) 是估价函数，并且估价函数要满足 f(state) <= g(state)，其中 g(state) 表示 state 到终点的真实距离；
5. A* 算法只能保证终点第一次出队时，即找到了一条从起点到终点的最小路径，不能保证其他点出队时也是从起点到当前点的最短路径。

class Solution:
  def openLock(self, deadends: List[str], target: str) -> int:
    def next(s):
      res = []
      s = list(s)
      for i in range(4):
        c = s[i]
        s[i] = '9' if c == '0' else str(int(c) - 1)
        res.append(''.join(s))
        s[i] = '0' if c == '9' else str(int(c) + 1)
        res.append(''.join(s))
        s[i] = c
      return res

    def f(s):
      ans = 0
      for i in range(4):
        a = ord(s[i]) - ord('0')
        b = ord(target[i]) - ord('0')
        if a > b:
          a, b = b, a
        ans += min(b - a, a + 10 - b)
      return ans

    if target == '0000':
      return 0
    s = set(deadends)
    if '0000' in s:
      return -1
    start = '0000'
    q = [(f(start), start)]
    dist = {start: 0}
    while q:
      _, state = heappop(q)
      if state == target:
        return dist[state]
      for t in next(state):
        if t in s:
          continue
        if t not in dist or dist[t] > dist[state] + 1:
          dist[t] = dist[state] + 1
          heappush(q, (dist[t] + f(t), t))
    return -1

class Solution {
  private String target;

  public int openLock(String[] deadends, String target) {
    if ("0000".equals(target)) {
      return 0;
    }
    String start = "0000";
    this.target = target;
    Set<String> s = new HashSet<>();
    for (String d : deadends) {
      s.add(d);
    }
    if (s.contains(start)) {
      return -1;
    }
    PriorityQueue<Pair<Integer, String>> q
      = new PriorityQueue<>(Comparator.comparingInt(Pair::getKey));
    q.offer(new Pair<>(f(start), start));
    Map<String, Integer> dist = new HashMap<>();
    dist.put(start, 0);
    while (!q.isEmpty()) {
      String state = q.poll().getValue();
      int step = dist.get(state);
      if (target.equals(state)) {
        return step;
      }
      for (String t : next(state)) {
        if (s.contains(t)) {
          continue;
        }
        if (!dist.containsKey(t) || dist.get(t) > step + 1) {
          dist.put(t, step + 1);
          q.offer(new Pair<>(step + 1 + f(t), t));
        }
      }
    }
    return -1;
  }

  private int f(String s) {
    int ans = 0;
    for (int i = 0; i < 4; ++i) {
      int a = s.charAt(i) - '0';
      int b = target.charAt(i) - '0';
      if (a > b) {
        int t = a;
        a = b;
        b = a;
      }
      ans += Math.min(b - a, a + 10 - b);
    }
    return ans;
  }

  private List<String> next(String t) {
    List res = new ArrayList<>();
    char[] chars = t.toCharArray();
    for (int i = 0; i < 4; ++i) {
      char c = chars[i];
      chars[i] = c == '0' ? '9' : (char) (c - 1);
      res.add(String.valueOf(chars));
      chars[i] = c == '9' ? '0' : (char) (c + 1);
      res.add(String.valueOf(chars));
      chars[i] = c;
    }
    return res;
  }
}

class Solution {
public:
  string target;

  int openLock(vector<string>& deadends, string target) {
    if (target == "0000") return 0;
    unordered_set<string> s(deadends.begin(), deadends.end());
    if (s.count("0000")) return -1;
    string start = "0000";
    this->target = target;
    typedef pair<int, string> PIS;
    priority_queue<PIS, vector<PIS>, greater<PIS>> q;
    unordered_map<string, int> dist;
    dist[start] = 0;
    q.push({f(start), start});
    while (!q.empty()) {
      PIS t = q.top();
      q.pop();
      string state = t.second;
      int step = dist[state];
      if (state == target) return step;
      for (string& t : next(state)) {
        if (s.count(t)) continue;
        if (!dist.count(t) || dist[t] > step + 1) {
          dist[t] = step + 1;
          q.push({step + 1 + f(t), t});
        }
      }
    }
    return -1;
  }

  int f(string s) {
    int ans = 0;
    for (int i = 0; i < 4; ++i) {
      int a = s[i] - '0';
      int b = target[i] - '0';
      if (a < b) {
        int t = a;
        a = b;
        b = t;
      }
      ans += min(b - a, a + 10 - b);
    }
    return ans;
  }

  vector<string> next(string& t) {
    vector<string> res;
    for (int i = 0; i < 4; ++i) {
      char c = t[i];
      t[i] = c == '0' ? '9' : (char) (c - 1);
      res.push_back(t);
      t[i] = c == '9' ? '0' : (char) (c + 1);
      res.push_back(t);
      t[i] = c;
    }
    return res;
  }
};