-
-
Notifications
You must be signed in to change notification settings - Fork 5.6k
/
752. Open the Lock.go
57 lines (55 loc) · 1.33 KB
/
752. Open the 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
57
package leetcode
func openLock(deadends []string, target string) int {
if target == "0000" {
return 0
}
targetNum, visited := strToInt(target), make([]bool, 10000)
visited[0] = true
for _, deadend := range deadends {
num := strToInt(deadend)
if num == 0 {
return -1
}
visited[num] = true
}
depth, curDepth, nextDepth := 0, []int16{0}, make([]int16, 0)
var nextNum int16
for len(curDepth) > 0 {
nextDepth = nextDepth[0:0]
for _, curNum := range curDepth {
for incrementer := int16(1000); incrementer > 0; incrementer /= 10 {
digit := (curNum / incrementer) % 10
if digit == 9 {
nextNum = curNum - 9*incrementer
} else {
nextNum = curNum + incrementer
}
if nextNum == targetNum {
return depth + 1
}
if !visited[nextNum] {
visited[nextNum] = true
nextDepth = append(nextDepth, nextNum)
}
if digit == 0 {
nextNum = curNum + 9*incrementer
} else {
nextNum = curNum - incrementer
}
if nextNum == targetNum {
return depth + 1
}
if !visited[nextNum] {
visited[nextNum] = true
nextDepth = append(nextDepth, nextNum)
}
}
}
curDepth, nextDepth = nextDepth, curDepth
depth++
}
return -1
}
func strToInt(str string) int16 {
return int16(str[0]-'0')*1000 + int16(str[1]-'0')*100 + int16(str[2]-'0')*10 + int16(str[3]-'0')
}