请选择 进入手机版 | 继续访问电脑版

走迷宫算法2(顺序栈 非最短路径)

[复制链接]
谢世民 发表于 2020-12-31 18:58:36 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
迷宫

二维数组来表现迷宫:
1)0表现可走的格子。
2)1表现墙。
初始化二维数组:
  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)

  1. /*        数据结构        顺序栈        走迷宫算法*/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
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )