共计 2285 个字符,预计需要花费 6 分钟才能阅读完成。
导读 | 这篇文章主要给大家介绍了关于 python 迷宫问题深度优先遍历的相关资料, 深度优先搜索算法 (Depth-First-Search), 是搜索算法的一种, 需要的朋友可以参考下 |
一、迷宫介绍
用 python 解迷宫问题,迷宫是一个二维列表,本次用深度优先解开迷宫问题。定义起点和终点,从一个位置到下一个位置只能通过向上或下或左或右,走一步来实现,从起点出发,如何找到一条到达终点的通路。
二、深度优先遍历
简单那我们的案例来讲就是,随便选择一条路,一直走,走不动了,再回头重新选择新的路
# 1 为墙,0 为路
maze = [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 1, 1, 0, 0, 0, 1, 1, 1],
[1, 0, 1, 1, 1, 1, 0, 0, 1, 1],
[1, 0, 1, 0, 0, 0, 0, 0, 1, 1],
[1, 0, 1, 0, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 0, 0, 0, 0, 1, 1, 1],
[1, 1, 1, 0, 0, 1, 0, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
]
首先我们先设置一个起点和终点
start = (1, 1)
end = (8, 8)
判断当前这个点,0 就是路可以走,1 为墙不能走
对于一个点的下一个点的坐标准说明:
- 上走:r – 1, c
- 下走:r + 1, c
- 左走:r, c – 1
- 右走:r, c + 1
那我们这个迷宫的某个一个点达到了不能走的地步了,就是死胡同了,它就得原路返回
这时我们就有一个概念,就是栈,栈的思想就是:先进后出
怎么理解呢,可以举一个小例子,就是食堂阿姨,每天早上蒸包子,他是一层一层放蒸笼
那放到最后,学生来吃包子,她是从上往往外拿,最上面就是最后放的,最下面是最先放的,所以就叫做先进后出
其实 list 就是一个栈,比如我们放一个空列表,然后我们用这个列表直接 append
再用 pop 进行取出,就会取到 append 的最后一个元素
# 定义列表,列表里面放的就是每一步走的坐标,[r, c]
# 第一步就是起始位置,也就是 start
list01 = [start]
走过的路定义为 2
row, col = now
# python 里的解构也叫解包 now 包括两个位置,一个行,一个列
maze[row][col] = 2
# 这个代表就是走过的点,为 2,因为你走过的路是不能再走的,除了走不通返回的时候,也是为了走不通按原来走过的路原路返回
核心代码:
if maze[row - 1][col] == 0:
# 上方可以走
list01.append((row - 1, col))
continue
elif maze[row][col + 1] == 0:
# 右方可以走
list01.append((row, col + 1))
continue
elif maze[row + 1][col] == 0:
# 下方可以走
list01.append((row + 1, col))
continue
elif maze[row][col - 1] == 0:
# 左方可以走
list01.append((row, col - 1))
continue
最终代码,可以运行一下试试:
maze = [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 0, 1, 1, 1], [1, 0, 1, 1, 1, 1, 0, 0, 1, 1], [1, 0, 1, 0, 0, 0, 0, 0, 1, 1], [1, 0, 1, 0, 1, 1, 1, 1, 1, 1], [1, 0, 0, 0, 1, 1, 1, 1, 1, 1], [1, 1, 1, 0, 0, 0, 0, 1, 1, 1], [1, 1, 1, 0, 0, 1, 0, 1, 1, 1], [1, 1, 1, 1, 1, 1, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], ]start = (1, 1) end = (8, 8)
# 定义列表,列表里面放的就是每一步走的坐标,[r, c] # 第一步就是起始位置,也就是 start list01 = [start]
# 定义循环,让它走 # 列表里最后存的就是下一步走的地方,当前列表有东西才能继续走 while list01: # 当前走到的节点是哪一个节点,也就是最后走的一步,是哪一步,去列表的最后的一个值就是索引 -1 now = list01[-1] if now == end: # 如果现在的 now 等于我们之前定义的终点 end print(list01) print("出来了") break row, col = now # python 里的解构也叫解包 now 包括两个位置,一个行,一个列 maze[row][col] = 2 # 这个代表就是走过的点,为 2,因为你走过的路是不能再走的,除了走不通返回的时候,也就是为了走不通按原来走过的路原路返回 # continue 结束本次循环,从新开始判断走路 if maze[row - 1][col] == 0: # 上方可以走 list01.append((row - 1, col)) continue elif maze[row][col + 1] == 0: # 右方可以走 list01.append((row, col + 1)) continue elif maze[row + 1][col] == 0: # 下方可以走 list01.append((row + 1, col)) continue elif maze[row][col - 1] == 0: # 左方可以走 list01.append((row, col - 1)) continue else: # 走不通过,直接循环干掉每一步,重新调整路线 list01.pop() else: print("这个迷宫走不通")
总结
到此这篇关于 python 迷宫问题深度优先遍历的文章就介绍到这了。
正文完
星哥说事-微信公众号
![post-qrcode](https://www.xgss.net/wp-content/uploads/2023/07/二维码-微信公众号256x256.jpg)