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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
|
// 贪心算法，通过bfs实现最短路径选择
func bfs(maze [][]int, begin []int, target []int, casVisited [][]bool) ([][][]int, int) {
var lastStep [][][]int
// 内部访问矩阵，这个访问矩阵只能保证本次从begin-target之间不重复
// casVisited级联的访问矩阵，使级联之间路径不重复
var visited [][]bool
for i := range maze {
visited = append(visited, make([]bool, len(maze[i])))
var line [][]int
for j := 0; j < len(maze[i]); j++ {
line = append(line, []int{-1, -1})
}
lastStep = append(lastStep, line)
}
q := [][]int{begin}
visited[begin[0]][begin[1]] = true
steps := 1
// 出队
for len(q) != 0 {
size := len(q)
for i := 0; i < size; i++ {
node := q[0]
x := node[0]
y := node[1]
q = q[1:]
if x == target[0] && y == target[1] {
return lastStep, steps
}
// 遍历
for _, step := range [][]int{{-1, 0}, {0, -1}, {1, 0}, {0, 1}} {
nextX := x + step[0]
nextY := y + step[1]
if nextX < 0 || nextX >= len(maze) {
continue
}
if nextY < 0 || nextY >= len(maze[x]) {
continue
}
if visited[nextX][nextY] {
continue
}
if casVisited[nextX][nextY] {
continue
}
if maze[nextX][nextY] == 1 {
continue
}
q = append(q, []int{nextX, nextY})
visited[nextX][nextY] = true
lastStep[nextX][nextY] = []int{x, y}
}
}
// 完成一层遍历，步数+1
steps++
}
return lastStep, steps
}
func trace(x, y int, lastStep [][][]int, casVisited [][]bool) {
if x == -1 && y == -1 {
return
}
now := lastStep[x][y]
casVisited[x][y] = true
trace(now[0], now[1], lastStep, casVisited)
}
func main(){
// 2 贪心算法， lastStep矩阵记录每一步的上一跳，steps记录步数
// 2.1 (0,0) => 三个金币点(2,5) (3,2) (5,1) 找到steps最短的下一跳，结果是(3,2)
fmt.Println("greedy:")
// 级联访问矩阵，保证每次级联不会重复上一次的路径
var casVisited [][]bool
for i := range maze {
casVisited = append(casVisited, make([]bool, len(maze[i])))
}
lastStep, steps := bfs(maze, []int{0, 0}, []int{3, 2}, casVisited)
for _, line := range lastStep {
fmt.Println(line)
}
fmt.Println(steps)
trace(3, 2, lastStep, casVisited)
// 2.2 (3,2) => (2,5) (5,1) 找到steps最短的下一跳，结果是(2,5)
lastStep, steps = bfs(maze, []int{3, 2}, []int{2, 5}, casVisited)
for _, line := range lastStep {
fmt.Println(line)
}
fmt.Println(steps)
trace(2, 5, lastStep, casVisited)
// 2.3 (2，5) => (5,1)
lastStep, steps = bfs(maze, []int{2, 5}, []int{5, 1}, casVisited)
for _, line := range lastStep {
fmt.Println(line)
}
fmt.Println(steps)
trace(5, 1, lastStep, casVisited)
// 2.4 (5，1) => (5,5) 结束
lastStep, steps = bfs(maze, []int{5, 1}, []int{5, 5}, casVisited)
for _, line := range lastStep {
fmt.Println(line)
}
fmt.Println(steps)
trace(5, 5, lastStep, casVisited)
for _, line := range casVisited {
fmt.Println(line)
}
// 2.5 三个lastStep按从(5,5)回溯到(0,0)就是最短路径
}
|