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
|
package main
import (
"fmt"
"sort"
"time"
)
func Min(list [][]int)[][]int{
var result [][][]int
var line [][]int
var dfs func(list [][]int, current []int)
dfs = func(list [][]int, current []int) {
// 获取当前位置xy轴
y, x := current[0], current[1]
// 出界返回, 继续下一个方向
if x >= len(list[0]) || x < 0 || y >= len(list) || y < 0 || list[y][x] == 1 {
return
}
// 记录已走过的路，以免走回头路
list[y][x] = 1
// 将当前坐标添加到线路切片中
line = append(line, []int{y, x})
// 记录当前线路状态，在此位置可能还有其他方向可以走
tmp := line
// 可视化
//for _, v := range list{
// fmt.Println(v)
//}
//fmt.Println()
//time.Sleep(time.Second)
// 如果到达终点
if x == len(list[0])-1 && y == len(list)-1{
// 还原已走过的路
list[y][x] = 0
// 必须拷贝，不然前面修改的路线位置无法获取
n := make([][]int, len(line))
copy(n, line)
// 记录成功结果线路
result = append(result, n)
return
}
// 向右走
dfs(list, []int{y, x+1})
line = tmp // 还原已走过的路
// 向下走
dfs(list, []int{y+1, x})
line = tmp // 还原已走过的路
// 向左走
dfs(list, []int{y, x-1})
line = tmp // 还原已走过的路
// 向上走
dfs(list, []int{y-1, x})
// 还原已走过的路
list[y][x] = 0
}
// 开始递归
dfs(list, []int{0, 0})
// 如果没有成功走到终点的线路，返回空
if len(result) == 0{
return nil
}
// 最短路径
sort.Slice(result, func(i, j int) bool {
return len(result[i]) < len(result[j])
})
fmt.Printf("共有线路: %d条\n", len(result))
return result[0]
// 共有几种走法
// return len(result)
}
func main() {
fmt.Println(time.Now())
list := [][]int{{0, 0, 0, 0, 1, 0, 1, 0, 0, 1},
{0, 0, 1, 0, 1, 1, 1, 1, 1, 0},
{0, 0, 0, 0, 1, 1, 0, 0, 0, 0},
{1, 0, 0, 0, 1, 1, 1, 1, 1, 0},
{0, 0, 1, 0, 0, 0, 0, 1, 0, 0},
{1, 0, 0, 1, 1, 0, 0, 0, 1, 0},
{0, 1, 0, 0, 0, 1, 1, 0, 1, 0},
{0, 0, 0, 1, 0, 0, 1, 0, 1, 0},
{0, 0, 1, 1, 1, 0, 0, 0, 0, 0},
{1, 1, 1, 0, 0, 0, 0, 0, 1, 0},
}
fmt.Println(Min(list))
fmt.Println(time.Now())
}
|
CloudNativeQingFeng