python迷宫问题深度优先遍历实例
作者:杨旭华啊 发布时间:2023-10-16 18:54:06
标签:python,深度,迷宫
一、迷宫介绍
用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("这个迷宫走不通")
总结
来源:https://blog.csdn.net/Yxh666/article/details/117887077
0
投稿
猜你喜欢
- 本文实例讲述了python装饰器原理与用法。分享给大家供大家参考,具体如下:你会Python嘛?我会!那你给我讲下Python装饰器吧!Py
- 前几天,使用python时遇到这么一个需求,删除一个列表中值为1的元素。我寻思着使用remove方法,但是remove方法只会删除第一个,于
- 无聊,写了一个图片后加载的东东,感谢asfman帮忙<!DOCTYPE html PUBLIC "-//W3C//DTD X
- 前言提示:这里可以添加本文要记录的大概内容:公司里B2B是通过WinSCP里SFTP与客户进行数据传输,WinSCP是一个Windows环境
- 1.建立设计规范的意义 建立设计文档的根本目的
- 读取docx文档使用的包是python-docx1. 安装python-docx包sudo pip install python-docx2
- 1 任务需求  首先,我们来明确一下本文所需实现的需求。  现有一个
- 最近 W3C 一口气推出 7 个 HTML 工作草案,涵盖了 HTML5,HTML RDF,HTML Microdata,HTM
- 目标:创建一个字典,记录几对python词语,使用OrderedDict类来写,并按顺序输出。写完报错:[root@centos7 tmp]
- 前言:pandas 中的索引意味着只需从系列中选择特定数据。索引可能意味着选择所有数据,其中一些数据来自特定列。索引也可以称为子集选择。使用
- 1、主题毫无疑问Pycharm是一个具有强大快捷键系统的IDE,这就意味着你在Pycharm中的任何操作,例如打开一个文件、切换编辑区域等,
- 函数带括号和不带括号的区别1、不带括号时,调用的是这个函数本身 ,是整个函数体,是一个函数对象,不需等该函数执行完成2、带括号(此
- 前言许多 Web 应用依赖大量的 I/O (输入/输出) 操作,比如从网站上下载图片、视频等内容;进行网络聊天或者针对后台数据库进行多次查询
- 本文实例为大家分享了python和pip安装教程,供大家参考,具体内容如下1.安装python第一步,windows下面的Python安装一
- 这篇文章主要介绍了python中删除某个元素的方法解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋
- 其实有一个疑惑一直在小编心中,每一个代码段编写里,总会出现好多个函数,也许有人和小编有一样的认同感,后来,小编明白,每一个函数本身都是都有各
- 类与实例类与实例相互关联着:类是对象的定义,而实例是“真正的实物”,它存放了类中所定义的对象的具体信息。下面的示例展示了如何创建一个类:cl
- 1.实现的思路(1)首先使用一个处理画框的程序,将图片中的有车和无车的停车位给画出来,并且保存坐标(如果画错了,将鼠标移至要删除的框中,右击
- 从这节开始,将会给大家介绍几个ASP中的三大通用类,它贯穿于我所设计的三层架构中,是对ASP语法的扩展,可以提高很多细节处理上的效率,可以算
- 因为很多时候要涉及到url的编码和解码工作,所以自己制作了一个类,废话不多说 码上见!# coding:utf-8import urllib