你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有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 <= 500deadends[i].length == 4target.length == 4target不在deadends之中target和deadends[i]仅由若干位数字组成
BFS 最小步数模型。
方法一：朴素 BFS
直接用朴素 BFS。
方法二：双向 BFS
本题也可以用双向 BFS 优化搜索空间，从而提升效率。
双向 BFS 是 BFS 常见的一个优化方法，主要实现思路如下：
-
创建两个队列 q1, q2 分别用于“起点 -> 终点”、“终点 -> 起点”两个方向的搜索；
-
创建两个哈希表 m1, m2 分别记录访问过的节点以及对应的扩展次数（步数）；
-
每次搜索时，优先选择元素数量较少的队列进行搜索扩展，如果在扩展过程中，搜索到另一个方向已经访问过的节点，说明找到了最短路径；
-
只要其中一个队列为空，说明当前方向的搜索已经进行不下去了，说明起点到终点不连通，无需继续搜索。
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
方法三：A*算法
A* 算法主要思想如下：
- 将 BFS 队列转换为优先队列（小根堆）；
- 队列中的每个元素为
(dist[state] + f(state), state)，dist[state]表示从起点到当前 state 的距离，f(state)表示从当前 state 到终点的估计距离，这两个距离之和作为堆排序的依据； - 当终点第一次出队时，说明找到了从起点到终点的最短路径，直接返回对应的 step；
f(state)是估价函数，并且估价函数要满足f(state) <= g(state)，其中g(state)表示 state 到终点的真实距离；- A* 算法只能保证终点第一次出队时，即找到了一条从起点到终点的最小路径，不能保证其他点出队时也是从起点到当前点的最短路径。
朴素 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双向 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
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()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朴素 BFS：
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;
}
}双向 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;
}
}A* 算法：
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;
}
}朴素 BFS：
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;
}
};双向 BFS 优化搜索：
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;
}
};A* 算法：
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;
}
};朴素 BFS：
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 优化搜索：
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()
}