LCR 109-打开转盘锁

Raphael Liu Lv10

一个密码锁由 4 个环形拨轮组成,每个拨轮都有 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
**解释:** 无法旋转到目标数字且不被锁定。

示例 4:

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

提示:

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

注意:本题与主站 752 题相同: https://leetcode-cn.com/problems/open-the-lock/

方法一:广度优先搜索

思路与算法

我们可以使用广度优先搜索,找出从初始数字 0000 到解锁数字 target 的最小旋转次数。

具体地,我们在一开始将 (0000, 0) 加入队列,并使用该队列进行广度优先搜索。在搜索的过程中,设当前搜索到的数字为 status,旋转的次数为 step,我们可以枚举 status 通过一次旋转得到的数字。设其中的某个数字为 next_status,如果其没有被搜索过,我们就将 (\textit{next_status}, \textit{step} + 1) 加入队列。如果搜索到了 target,我们就返回其对应的旋转次数。

为了避免搜索到死亡数字,我们可以使用哈希表存储 deadends 中的所有元素,这样在搜索的过程中,我们可以均摊 O(1) 地判断一个数字是否为死亡数字。同时,我们还需要一个哈希表存储所有搜索到的状态,避免重复搜索。

如果搜索完成后,我们仍没有搜索到 target,说明我们无法解锁,返回 -1。

细节

本题中需要注意如下两个细节:

  • 如果 target 就是初始数字 0000,那么直接返回答案 0;

  • 如果初始数字 0000 出现在 deadends 中,那么直接返回答案 -1。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public:
int openLock(vector<string>& deadends, string target) {
if (target == "0000") {
return 0;
}

unordered_set<string> dead(deadends.begin(), deadends.end());
if (dead.count("0000")) {
return -1;
}

auto num_prev = [](char x) -> char {
return (x == '0' ? '9' : x - 1);
};
auto num_succ = [](char x) -> char {
return (x == '9' ? '0' : x + 1);
};

// 枚举 status 通过一次旋转得到的数字
auto get = [&](string& status) -> vector<string> {
vector<string> ret;
for (int i = 0; i < 4; ++i) {
char num = status[i];
status[i] = num_prev(num);
ret.push_back(status);
status[i] = num_succ(num);
ret.push_back(status);
status[i] = num;
}
return ret;
};

queue<pair<string, int>> q;
q.emplace("0000", 0);
unordered_set<string> seen = {"0000"};

while (!q.empty()) {
auto [status, step] = q.front();
q.pop();
for (auto&& next_status: get(status)) {
if (!seen.count(next_status) && !dead.count(next_status)) {
if (next_status == target) {
return step + 1;
}
q.emplace(next_status, step + 1);
seen.insert(move(next_status));
}
}
}

return -1;
}
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
public int openLock(String[] deadends, String target) {
if ("0000".equals(target)) {
return 0;
}

Set<String> dead = new HashSet<String>();
for (String deadend : deadends) {
dead.add(deadend);
}
if (dead.contains("0000")) {
return -1;
}

int step = 0;
Queue<String> queue = new LinkedList<String>();
queue.offer("0000");
Set<String> seen = new HashSet<String>();
seen.add("0000");

while (!queue.isEmpty()) {
++step;
int size = queue.size();
for (int i = 0; i < size; ++i) {
String status = queue.poll();
for (String nextStatus : get(status)) {
if (!seen.contains(nextStatus) && !dead.contains(nextStatus)) {
if (nextStatus.equals(target)) {
return step;
}
queue.offer(nextStatus);
seen.add(nextStatus);
}
}
}
}

return -1;
}

public char numPrev(char x) {
return x == '0' ? '9' : (char) (x - 1);
}

public char numSucc(char x) {
return x == '9' ? '0' : (char) (x + 1);
}

// 枚举 status 通过一次旋转得到的数字
public List<String> get(String status) {
List<String> ret = new ArrayList<String>();
char[] array = status.toCharArray();
for (int i = 0; i < 4; ++i) {
char num = array[i];
array[i] = numPrev(num);
ret.add(new String(array));
array[i] = numSucc(num);
ret.add(new String(array));
array[i] = num;
}
return ret;
}
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
public class Solution {
public int OpenLock(string[] deadends, string target) {
if ("0000".Equals(target)) {
return 0;
}

ISet<string> dead = new HashSet<string>();
foreach (string deadend in deadends) {
dead.Add(deadend);
}
if (dead.Contains("0000")) {
return -1;
}

int step = 0;
Queue<string> queue = new Queue<string>();
queue.Enqueue("0000");
ISet<string> seen = new HashSet<string>();
seen.Add("0000");

while (queue.Count > 0) {
++step;
int size = queue.Count;
for (int i = 0; i < size; ++i) {
string status = queue.Dequeue();
foreach (string nextStatus in Get(status)) {
if (!seen.Contains(nextStatus) && !dead.Contains(nextStatus)) {
if (nextStatus.Equals(target)) {
return step;
}
queue.Enqueue(nextStatus);
seen.Add(nextStatus);
}
}
}
}

return -1;
}

public char NumPrev(char x) {
return x == '0' ? '9' : (char) (x - 1);
}

public char NumSucc(char x) {
return x == '9' ? '0' : (char) (x + 1);
}

// 枚举 status 通过一次旋转得到的数字
public IList<string> Get(string status) {
IList<string> ret = new List<string>();
char[] array = status.ToCharArray();
for (int i = 0; i < 4; ++i) {
char num = array[i];
array[i] = NumPrev(num);
ret.Add(new string(array));
array[i] = NumSucc(num);
ret.Add(new string(array));
array[i] = num;
}
return ret;
}
}
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
if target == "0000":
return 0

dead = set(deadends)
if "0000" in dead:
return -1

def num_prev(x: str) -> str:
return "9" if x == "0" else str(int(x) - 1)

def num_succ(x: str) -> str:
return "0" if x == "9" else str(int(x) + 1)

# 枚举 status 通过一次旋转得到的数字
def get(status: str) -> Generator[str, None, None]:
s = list(status)
for i in range(4):
num = s[i]
s[i] = num_prev(num)
yield "".join(s)
s[i] = num_succ(num)
yield "".join(s)
s[i] = num

q = deque([("0000", 0)])
seen = {"0000"}
while q:
status, step = q.popleft()
for next_status in get(status):
if next_status not in seen and next_status not in dead:
if next_status == target:
return step + 1
q.append((next_status, step + 1))
seen.add(next_status)

return -1
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
var openLock = function(deadends, target) {
if (target === '0000') {
return 0;
}

const dead = new Set(deadends);
if (dead.has("0000")) {
return -1;
}

let step = 0;
const queue = [];
queue.push("0000");
const seen = new Set();
seen.add("0000");

while (queue.length) {
++step;
const size = queue.length;
for (let i = 0; i < size; ++i) {
const status = queue.shift();
for (const nextStatus of get(status)) {
if (!seen.has(nextStatus) && !dead.has(nextStatus)) {
if (nextStatus === target) {
return step;
}
queue.push(nextStatus);
seen.add(nextStatus);
}
}
}
}

return -1;
};

const numPrev = (x) => {
return x === '0' ? '9' : (parseInt(x) - 1) + '';
}

const numSucc = (x) => {
return x === '9' ? '0' : (parseInt(x) + 1) + '';
}

// 枚举 status 通过一次旋转得到的数字
const get = (status) => {
const ret = [];
const array = Array.from(status);
for (let i = 0; i < 4; ++i) {
const num = array[i];
array[i] = numPrev(num);
ret.push(array.join(''));
array[i] = numSucc(num);
ret.push(array.join(''));
array[i] = num;
}

return ret;
}
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
func openLock(deadends []string, target string) int {
const start = "0000"
if target == start {
return 0
}

dead := map[string]bool{}
for _, s := range deadends {
dead[s] = true
}
if dead[start] {
return -1
}

// 枚举 status 通过一次旋转得到的数字
get := func(status string) (ret []string) {
s := []byte(status)
for i, b := range s {
s[i] = b - 1
if s[i] < '0' {
s[i] = '9'
}
ret = append(ret, string(s))
s[i] = b + 1
if s[i] > '9' {
s[i] = '0'
}
ret = append(ret, string(s))
s[i] = b
}
return
}

type pair struct {
status string
step int
}
q := []pair{ {start, 0} }
seen := map[string]bool{start: true}
for len(q) > 0 {
p := q[0]
q = q[1:]
for _, nxt := range get(p.status) {
if !seen[nxt] && !dead[nxt] {
if nxt == target {
return p.step + 1
}
seen[nxt] = true
q = append(q, pair{nxt, p.step + 1})
}
}
}
return -1
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
struct HashTable {
char str[5];
UT_hash_handle hh;
};

struct Node {
char str[5];
int val;
};

char num_prev(char x) {
return (x == '0' ? '9' : x - 1);
}

char num_succ(char x) {
return (x == '9' ? '0' : x + 1);
}

// 枚举 status 通过一次旋转得到的数字
char** getNextStatus(char* status, int* retSize) {
char** ret = malloc(sizeof(char*) * 8);
*retSize = 0;
for (int i = 0; i < 4; ++i) {
char num = status[i];
status[i] = num_prev(num);
ret[(*retSize)] = malloc(sizeof(char) * 5);
strcpy(ret[(*retSize)++], status);
status[i] = num_succ(num);
ret[(*retSize)] = malloc(sizeof(char) * 5);
strcpy(ret[(*retSize)++], status);
status[i] = num;
}
return ret;
}

int openLock(char** deadends, int deadendsSize, char* target) {
char str_0[5] = "0000";
if (strcmp(target, str_0) == 0) {
return 0;
}
struct HashTable* dead = NULL;
struct HashTable* tmp;
for (int i = 0; i < deadendsSize; i++) {
HASH_FIND(hh, dead, deadends[i], sizeof(char) * 5, tmp);
if (tmp == NULL) {
tmp = malloc(sizeof(struct HashTable));
strcpy(tmp->str, deadends[i]);
HASH_ADD(hh, dead, str, sizeof(char) * 5, tmp);
}
}
HASH_FIND(hh, dead, str_0, sizeof(char) * 5, tmp);

if (tmp != NULL) {
return -1;
}

struct Node q[10001];
int left = 0, right = 0;
strcpy(q[right].str, str_0);
q[right++].val = 0;

struct HashTable* seen = NULL;
tmp = malloc(sizeof(struct HashTable));
strcpy(tmp->str, str_0);
HASH_ADD(hh, seen, str, sizeof(char) * 5, tmp);

while (left < right) {
char* status = q[left].str;
int step = q[left++].val;
int nextStatusSize;
char** nextStatus = getNextStatus(status, &nextStatusSize);
for (int i = 0; i < nextStatusSize; i++) {
struct HashTable *tmp1, *tmp2;
HASH_FIND(hh, dead, nextStatus[i], sizeof(char) * 5, tmp1);
HASH_FIND(hh, seen, nextStatus[i], sizeof(char) * 5, tmp2);
if (tmp1 == NULL && tmp2 == NULL) {
if (strcmp(nextStatus[i], target) == 0) {
return step + 1;
}
strcpy(q[right].str, nextStatus[i]);
q[right++].val = step + 1;
tmp = malloc(sizeof(struct HashTable));
strcpy(tmp->str, nextStatus[i]);
HASH_ADD(hh, seen, str, sizeof(char) * 5, tmp);
}
}
}

return -1;
}

复杂度分析

  • 时间复杂度:O(b^d \cdot d^2 + md),其中 b 是数字的进制,d 是拨轮数字的位数,m 是数组 deadends 的长度,在本题中 b=10,d=4。

    • 拨轮数字的可能性一共有 b^d 种,这也是我们可以搜索到的状态数上限。对于每一个拨轮数字,我们需要 O(d) 的时间枚举旋转的数位,同时需要 O(d) 的时间生成旋转后的数字(即加入队列),因此广度优先搜索的总时间复杂度为 O(b^d \cdot d^2)。

    • 此外,在搜索前我们需要将 deadends 中的所有元素放入哈希表中,计算一个字符串哈希值需要的时间为 O(d),因此需要的总时间为 O(md)。

  • 空间复杂度:O(b^d \cdot d + m)。

    • 我们最多需要在队列中存储 O(b^d) 个长度为 d 的字符串,空间复杂度为 O(b^d \cdot d);

    • 哈希表需要 O(m) 的空间。如果使用的语言存储的是元素的拷贝,那么需要的空间为 O(md)。

方法二:启发式搜索

概念

我们可以使用启发式搜索更快地找到最小旋转次数。这里我们可以使用 A* 算法。

读者可以自行查阅资料学习关于 A* 算法的基础知识,例如 Wikipedia - A* search algorithm oi-wiki - A* 。它不是本题解的重点,因此这里不再赘述。读者可以阅读下面的段落检验自己的学习成果:

在 A* 算法中,我们需要使用四个距离函数 F(x), G(x), H(x), H^*(x),其中 F(x), G(x), H(x) 是可以求出的,而 H^*(x) 是无法求出的,我们需要用 H(x) 近似 H^*(x)。设起点为 s,终点为 t,这些距离函数的意义如下:

  • G(x) 表示从起点 s 到节点 x 的「实际」路径长度,注意 G(x) 并不一定是最短的;

  • H(x) 表示从节点 x 到终点 t 的「估计」最短路径长度,称为启发函数

  • H^*(x) 表示从节点 x 到终点 t 的「实际」最短路径长度,这是我们在广度优先搜索的过程中无法求出的,我们需要用 H(x) 近似 H^*(x);

  • F(x) 满足 F(x) = G(x) + H(x),即为从起点 s 到终点 t 的「估计」路径长度。我们总是挑选出最小的 F(x) 对应的 x 进行搜索,因此 A* 算法需要借助优先队列来实现。

如果读者熟悉求解最短路的 Dijkstra 算法,就可以发现 Dijkstra 算法是 A* 算法在 H(x) \equiv 0 时的特殊情况。

A* 算法具有两个性质:

  • 如果对于任意的节点 x,H(x) \leq H^*(x) 恒成立,即我们「估计」出的从节点 x 到终点 t 的最短路径长度总是不超过「实际」的最短路径长度,那么称启发函数 H(x) 是可接纳的(admissible heuristic)。在这种情况下,A* 算法一定能找到最短路,但同一节点可能需要加入优先队列并搜索多次,即当我们从优先队列中取出节点 x 时,G(x) 并不一定等于从起点到节点 x 的「实际」最短路径的长度;

  • 如果对于任意的两个节点 x 和 y,并且 x 到 y 有一条长度为 D(x, y) 的有向边,H(x) - H(y) \leq D(x, y) 恒成立,并且 H(t)=0,那么称启发函数 H(x) 是一致的(consistent heuristic)。可以证明,一致的启发函数一定也是可接纳的。在这种情况下,同一节点只会被加入优先队列一次,并搜索不超过一次,即当我们从优先队列中取出节点 x 时,G(x) 一定等于从起点到节点 x 的「实际」最短路径的长度。

思路与算法

我们可以设计如下的启发函数:

H(\textit{status}) = \sum_{i=0}^3
\left( \begin{aligned}
& 将 \textit{status} 的第 i 个数字旋转到与 \textit{target} 的第 i 个数字一致,\
& 最少需要的次数
\end{aligned} \right)

即 H(\textit{status}) 等于不存在死亡数字时最小的旋转次数。根据定义,对于数字 status 和其通过一次旋转得到的数字 next_status,H(\textit{status}) - H(\textit{next_status}) 要么为 1(旋转的那一个数位与 target 更近了),要么为 -1(旋转的那一个数位与 target 更远了),而 D(\textit{status}, \textit{next_status}) = 1,因此我们设计的启发函数是一致的。

我们在 A* 算法中使用该启发函数,即可得到最小的旋转次数。

代码

[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
struct AStar {
// 计算启发函数
static int getH(const string& status, const string& target) {
int ret = 0;
for (int i = 0; i < 4; ++i) {
int dist = abs(int(status[i]) - int(target[i]));
ret += min(dist, 10 - dist);
}
return ret;
};

AStar(const string& status, const string& target, int g): status_{status}, g_{g}, h_{getH(status, target)} {
f_ = g_ + h_;
}

bool operator< (const AStar& that) const {
return f_ > that.f_;
}

string status_;
int f_, g_, h_;
};

class Solution {
public:
int openLock(vector<string>& deadends, string target) {
if (target == "0000") {
return 0;
}

unordered_set<string> dead(deadends.begin(), deadends.end());
if (dead.count("0000")) {
return -1;
}

auto num_prev = [](char x) -> char {
return (x == '0' ? '9' : x - 1);
};
auto num_succ = [](char x) -> char {
return (x == '9' ? '0' : x + 1);
};

auto get = [&](string& status) -> vector<string> {
vector<string> ret;
for (int i = 0; i < 4; ++i) {
char num = status[i];
status[i] = num_prev(num);
ret.push_back(status);
status[i] = num_succ(num);
ret.push_back(status);
status[i] = num;
}
return ret;
};

priority_queue<AStar> q;
q.emplace("0000", target, 0);
unordered_set<string> seen = {"0000"};

while (!q.empty()) {
AStar node = q.top();
q.pop();
for (auto&& next_status: get(node.status_)) {
if (!seen.count(next_status) && !dead.count(next_status)) {
if (next_status == target) {
return node.g_ + 1;
}
q.emplace(next_status, target, node.g_ + 1);
seen.insert(move(next_status));
}
}
}

return -1;
}
};
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class Solution {
public int openLock(String[] deadends, String target) {
if ("0000".equals(target)) {
return 0;
}

Set<String> dead = new HashSet<String>();
for (String deadend : deadends) {
dead.add(deadend);
}
if (dead.contains("0000")) {
return -1;
}

PriorityQueue<AStar> pq = new PriorityQueue<AStar>((a, b) -> a.f - b.f);
pq.offer(new AStar("0000", target, 0));
Set<String> seen = new HashSet<String>();
seen.add("0000");

while (!pq.isEmpty()) {
AStar node = pq.poll();
for (String nextStatus : get(node.status)) {
if (!seen.contains(nextStatus) && !dead.contains(nextStatus)) {
if (nextStatus.equals(target)) {
return node.g + 1;
}
pq.offer(new AStar(nextStatus, target, node.g + 1));
seen.add(nextStatus);
}
}
}

return -1;
}

public char numPrev(char x) {
return x == '0' ? '9' : (char) (x - 1);
}

public char numSucc(char x) {
return x == '9' ? '0' : (char) (x + 1);
}

// 枚举 status 通过一次旋转得到的数字
public List<String> get(String status) {
List<String> ret = new ArrayList<String>();
char[] array = status.toCharArray();
for (int i = 0; i < 4; ++i) {
char num = array[i];
array[i] = numPrev(num);
ret.add(new String(array));
array[i] = numSucc(num);
ret.add(new String(array));
array[i] = num;
}
return ret;
}
}

class AStar {
String status;
int f, g, h;

public AStar(String status, String target, int g) {
this.status = status;
this.g = g;
this.h = getH(status, target);
this.f = this.g + this.h;
}

// 计算启发函数
public static int getH(String status, String target) {
int ret = 0;
for (int i = 0; i < 4; ++i) {
int dist = Math.abs(status.charAt(i) - target.charAt(i));
ret += Math.min(dist, 10 - dist);
}
return ret;
}
}
[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class AStar:
# 计算启发函数
@staticmethod
def getH(status: str, target: str) -> int:
ret = 0
for i in range(4):
dist = abs(int(status[i]) - int(target[i]))
ret += min(dist, 10 - dist)
return ret

def __init__(self, status: str, target: str, g: str) -> None:
self.status = status
self.g = g
self.h = AStar.getH(status, target)
self.f = self.g + self.h

def __lt__(self, other: "AStar") -> bool:
return self.f < other.f

class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
if target == "0000":
return 0

dead = set(deadends)
if "0000" in dead:
return -1

def num_prev(x: str) -> str:
return "9" if x == "0" else str(int(x) - 1)

def num_succ(x: str) -> str:
return "0" if x == "9" else str(int(x) + 1)

def get(status: str) -> Generator[str, None, None]:
s = list(status)
for i in range(4):
num = s[i]
s[i] = num_prev(num)
yield "".join(s)
s[i] = num_succ(num)
yield "".join(s)
s[i] = num

q = [AStar("0000", target, 0)]
seen = {"0000"}
while q:
node = heapq.heappop(q)
for next_status in get(node.status):
if next_status not in seen and next_status not in dead:
if next_status == target:
return node.g + 1
heapq.heappush(q, AStar(next_status, target, node.g + 1))
seen.add(next_status)

return -1
[sol2-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
type astar struct {
g, h int
status string
}
type hp []astar

func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].g+h[i].h < h[j].g+h[j].h }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{}) { *h = append(*h, v.(astar)) }
func (h *hp) Pop() interface{} { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

// 计算启发函数
func getH(status, target string) (ret int) {
for i := 0; i < 4; i++ {
dist := abs(int(status[i]) - int(target[i]))
ret += min(dist, 10-dist)
}
return
}

func openLock(deadends []string, target string) int {
const start = "0000"
if target == start {
return 0
}

dead := map[string]bool{}
for _, s := range deadends {
dead[s] = true
}
if dead[start] {
return -1
}

get := func(status string) (ret []string) {
s := []byte(status)
for i, b := range s {
s[i] = b - 1
if s[i] < '0' {
s[i] = '9'
}
ret = append(ret, string(s))
s[i] = b + 1
if s[i] > '9' {
s[i] = '0'
}
ret = append(ret, string(s))
s[i] = b
}
return
}

type pair struct {
status string
step int
}
h := hp{ {0, getH(start, target), start} }
seen := map[string]bool{start: true}
for len(h) > 0 {
node := heap.Pop(&h).(astar)
for _, nxt := range get(node.status) {
if !seen[nxt] && !dead[nxt] {
if nxt == target {
return node.g + 1
}
seen[nxt] = true
heap.Push(&h, astar{node.g + 1, getH(nxt, target), nxt})
}
}
}
return -1
}

func abs(x int) int {
if x < 0 {
return -x
}
return x
}

func min(a, b int) int {
if a < b {
return a
}
return b
}

复杂度分析

启发式搜索不讨论时空复杂度。

 Comments
On this page
LCR 109-打开转盘锁