迷宫
用二维数组来表现迷宫：
1）0表现可走的格子。
2）1表现墙。
初始化二维数组：
- mazeMap := [10][10]int{ {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 0, 0, 1, 0, 0, 0, 1, 0, 1}, {1, 0, 0, 1, 0, 0, 0, 1, 0, 1}, {1, 0, 0, 0, 0, 1, 1, 0, 0, 1}, {1, 0, 1, 1, 1, 0, 0, 0, 0, 1}, {1, 0, 0, 0, 1, 0, 0, 0, 0, 1}, {1, 0, 1, 0, 0, 0, 1, 0, 0, 1}, {1, 0, 1, 1, 1, 0, 1, 1, 0, 1}, {1, 1, 0, 0, 0, 0, 0, 0, 0, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, }
算法思路
用顺序栈来生存走迷宫的路径，生存可行路径每一步的坐标。
假设起点坐标（1，1）可以走，那么把起点路标压入栈。
然后从起点位置按照上、右、下、左的顺序，访问相邻的格子。
遇到可以走的格子，则把格子的坐标压入栈，如图所示：
首先往栈中压入起点坐标（1，1）。
按照上、右、下、左的顺序，假设从坐标（1，1）开始往上走到坐标（0，1）。
先把坐标（0，1）压入栈。
背面判断坐标（0，1）为不可走的格子后，把坐标（0，1）弹出栈，如图所示：
以此循环，直到栈顶元素的坐标为终点坐标，说明乐成找到了走迷宫的路径，竣事步调。
代码（Golang）
- /* 数据结构 顺序栈 走迷宫算法*/package mainimport "fmt"type Box struct { x int // 横坐标 y int // 纵坐标 direction int // 方向}type Stack struct { data [50]Box top int}func mazePath(startX int, startY int, endX int, endY int, path *Stack, mazeMap *[10][10]int) bool { var ( x int y int direction int // 方向 find int // 标识是否可走 ) path.top = -1 // 初始化栈顶元素 // 将起点压入栈 path.top++ path.data[path.top].x = startX path.data[path.top].y = startY // 初始化走相邻格子的方向 path.data[path.top].direction = -1 mazeMap[startX][startY] = -1 for path.top > -1 { // 每次将格子坐标、方向压入栈 // 不可走的格子坐标、方向后续将会被弹出栈 x = path.data[path.top].x y = path.data[path.top].y direction = path.data[path.top].direction // 走到了终点，竣事步调 // 返回函数执行结果为 true if x == endX && y == endY { return true } // 某方向的相邻格子是否能走 // 如果能走，find 置为 1 find = 0 for direction < 4 && find == 0 { direction++ // 探索相邻的格子 // direction = 0 向上探索 // direction = 1 向右探索 // direction = 2 向下探索 // direction = 3 向左探索 switch direction { case 0: x = path.data[path.top].x - 1 y = path.data[path.top].y case 1: x = path.data[path.top].x y = path.data[path.top].y + 1 case 2: x = path.data[path.top].x + 1 y = path.data[path.top].y case 3: x = path.data[path.top].x y = path.data[path.top].y - 1 } // 说明该方向的格子可以走 // 把 find 置为 1，竣事搜索方向的 for 循环 if mazeMap[x][y] == 0 { find = 1 } } // 如果该方向可以走，则把该方向的格子压入栈 if find == 1 { path.data[path.top].direction = direction path.top++ path.data[path.top].x = x path.data[path.top].y = y path.data[path.top].direction = -1 mazeMap[x][y] = -1 } else { // 如果不能走，则把该方向的格子弹出栈 mazeMap[path.data[path.top].x][path.data[path.top].y] = 0 path.top-- } } // 如果走不到终点，说明该迷宫问题无解 return false}func main() { // 初始化迷宫舆图 // 用二维数组来表现 mazeMap := [10][10]int{ {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 0, 0, 1, 0, 0, 0, 1, 0, 1}, {1, 0, 0, 1, 0, 0, 0, 1, 0, 1}, {1, 0, 0, 0, 0, 1, 1, 0, 0, 1}, {1, 0, 1, 1, 1, 0, 0, 0, 0, 1}, {1, 0, 0, 0, 1, 0, 0, 0, 0, 1}, {1, 0, 1, 0, 0, 0, 1, 0, 0, 1}, {1, 0, 1, 1, 1, 0, 1, 1, 0, 1}, {1, 1, 0, 0, 0, 0, 0, 0, 0, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, } var ( startX int = 1 // 起点横坐标 startY int = 1 // 起点纵坐标 endX int = 8 // 终点横坐标 endY int = 8 // 终点纵坐标 ) // 初始化栈 path := &Stack{} // 如果迷宫问题有解 // 输出走迷宫的步调 if mazePath(startX, startY, endX, endY, path, &mazeMap) { for i := 0; i (1,1)第 2 步 ===> (1,2)第 3 步 ===> (2,2)第 4 步 ===> (3,2)第 5 步 ===> (3,1)第 6 步 ===> (4,1)第 7 步 ===> (5,1)第 8 步 ===> (5,2)第 9 步 ===> (5,3)第 10 步 ===> (6,3)第 11 步 ===> (6,4)第 12 步 ===> (6,5)第 13 步 ===> (5,5)第 14 步 ===> (4,5)第 15 步 ===> (4,6)第 16 步 ===> (4,7)第 17 步 ===> (3,7)第 18 步 ===> (3,8)第 19 步 ===> (4,8)第 20 步 ===> (5,8)第 21 步 ===> (6,8)第 22 步 ===> (7,8)第 23 步 ===> (8,8)
小结
可以发现，最后解出的走迷宫路径不是最短路径，这和设置的寻路战略有关。
因为设置的寻路战略为（上、右、下、左）因此步调只会按照这个寻路顺序来走迷宫。
后续将会更新走迷宫的最短路径算法。
来源：https://blog.csdn.net/a451343010/article/details/111993383
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ |
