广度优先算法走迷宫

广度优先遍历，走迷宫思路：

  1. 创建二维数组，0表示是路，1表示是墙；创建队列Q，存储可遍历的点，Q的第一个元素为起始点

  2. 从队列中取一个点，开始，按上、左、下、右的顺序遍历周围的点next，next点在数组的范围内，且值为0，则把next存入队列Q中，并在steps（行走记录二维数组）中记录步数，该点周围的四个点遍历完后,从Q中取下一个点，重复以上步骤，直到Q中没有点或者当前点为终点为止

  3. 最后打印steps即为迷宫路线

maze.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
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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
package main

import (
	"fmt"
	"os"
)

func readFile(filename string) [][]int {
	// 定义一个行和列,用来接收迷宫是几行几列的数组
	var row, col int
	file, e := os.Open(filename)
	if e != nil {
		panic("error")
	}
	defer file.Close()

	fmt.Fscan(file, &row, &col)

	// 定义一个数组
	// 注意: 定义数组的时候, 我们只要传入几行就可以了.
	// 二维数组的含义, 其实质是一个一维数组, 一维数组里每一个元素又是一个数组
	maze := make([][]int, row)
	for i := 0; i < len(maze); i++ {
		maze[i] = make([]int, col)
		for j := 0; j < len(maze[i]); j++ {
			fmt.Fscan(file, &maze[i][j])
		}
	}

	return maze
}

type point struct {
	i, j int
}

// 当前节点, 向四个方向探索后的节点
// 这里使用的是返回新的节点的方式, 不修改原来的节点. 所以使用的是值拷贝,而不是传地址
func (p point) add(dir point) point {
	return point{p.i + dir.i, p.j + dir.j}
}

// 获取某个点的坐标值
// 同时判断这个点有没有越界, 返回的是这个值是否有效
// return 第一个参数表示返回的值是否是1, 是1表示撞墙了
//        第二个参数表示返回的值是否不越界, 不越界返回true, 越界,返回false 就和你
func (p point) at(grid [][]int) (int, bool) {
	if p.i < 0 || p.i >= len(grid) {
		return 0, false
	}

	if p.j < 0 || p.j >= len(grid[0]) {
		return 0, false
	}
	return grid[p.i][p.j], true
}

// 定义要探索的方向, 上下左右四个方向
var dirs = []point{
	point{-1, 0},
	point{0, -1},
	point{1, 0},
	point{0, 1},
}

// 走迷宫
func walk(maze [][]int, start, end point) [][]int {
	// 第一步: step代表从start开始, 走了多少步走到目标点, 最后的路径是通过这个创建出来的, 最后从后往前推就可以算出最短路径
	// 2. 通step还可以知道哪些点是到过的, 哪些点是没到过的
	step := make([][]int, len(maze))
	for i := range step {
		// 定义每一行有多少列, 这样就定义了一个和迷宫一样的二维数组
		step[i] = make([]int, len(maze[i]))
	}

	// 第二步: 定义一个队列, 用来保存已经发现还未探索的点, 队列里的初始值是(0,0)点
	Que := []point{start}

	// 第三步: 开始走迷宫, 走迷宫退出的条件有两个
	// 1. 走到终点, 退出
	// 2. 队列中没有元素, 退出
	for len(Que) > 0 {
		// 开始探索, 依次取出队列中, 已经发现还未探索的元素
		// cur 表示当前要探索的节点
		cur := Que[0]
		// 然后从头拿掉第一个元素
		Que = Que[1:]

		// 如果这个点是终点, 就不向下探索了
		if cur == end {
			break
		}

		// 当前节点怎么探索呢? 要往上下左右四个方向去探索
		for _, dir := range dirs {
			// 探索下一个节点, 这里获取下一个节点的坐标. 当前节点+方向
			next := cur.add(dir)
			// 判断坐标是否符合探索的要求
			// 1. maze at next is 0
			// 2. and setp at next is 0, 如果step的值不是0 ,说明曾经到过这个点了, 不能重复走
			// 3. next != start 处理特殊点, (0,0)点

			// 探索这个点是否是墙
			val, ok := next.at(maze)
			if !ok || val == 1 {
				continue
			}

			// 探索这个点是否已经走过
			val, ok = next.at(step)
			if val != 0 || !ok {
				continue
			}

			// 走到起始点了, 返回
			if next == start {
				continue
			}

			// 已经找到这个点了, 计算当前的步数
			curval, _ := cur.at(step)         // 当前这一步的步数
			step[next.i][next.j] = curval + 1 // 下一步是当前步数+1
			Que = append(Que, next)           // 将下一步节点放入到队列中
		}

	}
	return step
}

func main() {

	maze := readFile("maze/maze.in")

	steps := walk(maze, point{0, 0}, point{len(maze) - 1, len(maze[0]) - 1})
	// len(maze)-1, len[maze[0]]-1 是终点
	// 0,0是起始点
	for _, row := range steps {
		for _, val := range row {
			fmt.Printf("%3d", val)
		}
		fmt.Println()
	}
}

maze.in 文件内容

6 5
0 1 0 0 0
0 0 0 1 0
0 1 0 1 0
1 1 1 0 0
0 1 0 0 1
0 1 0 0 0