-
Notifications
You must be signed in to change notification settings - Fork 1
/
open_lock.go
56 lines (49 loc) · 1.16 KB
/
open_lock.go
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
package _752_open_the_lock
import "strconv"
func openLock(deadends []string, target string) int {
t, _ := strconv.Atoi(target)
if t == 0 {
return 0
}
deadendsMap := [10_000]bool{}
for _, deadend := range deadends {
n, _ := strconv.Atoi(deadend)
deadendsMap[n] = true
}
if deadendsMap[0] {
return -1
}
counter, queue, visited := 0, []int{0}, [10_000]bool{}
visited[0] = true
for len(queue) != 0 {
counter++
for _, combination := range queue {
queue = queue[1:]
for _, candidate := range getAllCandidates(combination) {
if candidate == t {
return counter
}
if !deadendsMap[candidate] && !visited[candidate] {
visited[candidate] = true
queue = append(queue, candidate)
}
}
}
}
return -1
}
func getAllCandidates(combination int) []int {
result := make([]int, 0, 8)
for place := 1; place <= 1_000; place *= 10 {
d := (combination / place) % 10
switch d {
case 0:
result = append(result, combination+9*place, combination+place)
case 9:
result = append(result, combination-9*place, combination-place)
default:
result = append(result, combination-place, combination+place)
}
}
return result
}