Python基于递归算法实现的走迷宫问题
作者:叶赫那拉坤 发布时间:2023-08-25 03:55:05
标签:Python,递归算法
本文实例讲述了Python基于递归算法实现的走迷宫问题。分享给大家供大家参考,具体如下:
什么是递归?
简单地理解就是函数调用自身的过程就称之为递归。
什么时候用到递归?
如果一个问题可以表示为更小规模的迭代运算,就可以使用递归算法。
迷宫问题:一个由0或1构成的二维数组中,假设1是可以移动到的点,0是不能移动到的点,如何从数组中间一个值为1的点出发,每一只能朝上下左右四个方向移动一个单位,当移动到二维数组的边缘,即可得到问题的解,类似的问题都可以称为迷宫问题。
在python中可以使用list嵌套表示二维数组。假设一个6*6的迷宫,问题时从该数组坐标[3][3]出发,判断能不能成功的走出迷宫。
maze=[[1,0,0,1,0,1],
[1,1,1,0,1,0],
[0,0,1,0,1,0],
[0,1,1,1,0,0],
[0,0,0,1,0,0],
[1,0,0,0,0,0]]
针对这个迷宫问题,我们可以使用递归的思想很好的解决。对于数组中的一个点,该点的四个方向可以通过横纵坐标的加减轻松的表示,每当移动的一个可移动的点时候,整个问题又变为和初始状态一样的问题,继续搜索四个方向找可以移动的点,知道移动到数组的边缘。
所以我们可以这样编码:
# 判断坐标的有效性,如果超出数组边界或是不满足值为1的条件,说明该点无效返回False,否则返回True。
def valid(maze,x,y):
if (x>=0 and x<len(maze) and y>=0 and y<len(maze[0]) and maze[x][y]==1):
return True
else:
return False
# 移步函数实现
def walk(maze,x,y):
# 如果位置是迷宫的出口,说明成功走出迷宫
if(x==0 and y==0):
print("successful!")
return True
# 递归主体实现
if valid(maze,x,y):
# print(x,y)
maze[x][y]=2 # 做标记,防止折回
# 针对四个方向依次试探,如果失败,撤销一步
if not walk(maze,x-1,y):
maze[x][y]=1
elif not walk(maze,x,y-1):
maze[x][y]=1
elif not walk(maze,x+1,y):
maze[x][y]=1
elif not walk(maze,x,y+1):
maze[x][y]=1
else:
return False # 无路可走说明,没有解
return True
walk(maze,3,3)
递归是个好东西呀!
PS:本站还有一个无限迷宫游戏,基于JS实现,提供给大家参考一下:
在线迷宫小游戏:
http://tools.jb51.net/games/migong
希望本文所述对大家Python程序设计有所帮助。
0
投稿
猜你喜欢
- 1、准备工作安装好Pycharm2017版本电脑上安装好Python解释器2、本地解释器配置配置本地解释器的步骤相对简洁直观:(1)单击工具
- 当元素设置浮动(float)后会被移出文档流,相信大家都会经常遇到这样的问题。这问题的解决办法有N种之多,因为每种浏览器对CSS的解析各异,
- 微博模拟登录这是本次爬取的网址:https://weibo.com/一、请求分析找到登录的位置,填写用户名密码进行登录操作看看这次请求响应的
- 本文实例讲述了Python redis操作。分享给大家供大家参考,具体如下:一、redisredis是一个key-value存储系统。和Me
- XML是一个精简的SGML,它将SGML的丰富功能与HTML的易用性结合到Web的应用中。XML保留了SGML的可扩展功能,这使XML从根本
- 凯撒加密就是通过将字母移动一定的位数来实现加密和解密。明文中的所有字母都在字母表上向后(或向前)按照一个固定数目进行偏移,被替换成密文。例如
- 引言要说在工作中最让人头疼的就是用同样的方式处理一堆文件夹中文件,这并不难,但就是繁。所以在遇到机械式的操作时一定要记得使用Python来合
- 1.lambda表达式一般用法语法:lamda argument:expressionexample:add = lambda x, y:
- 终于开始做用户部分了,先做注册一用户 1.1用户注册 首先在Models里添加用户注册模型类UserRegister 继
- python有很多有趣的库,其中wxpy是连接微信的接口,具体可以查看官方文档。可以实现自动操作,wxpy 支持 Python 3.4-3.
- jupyter中显示的DataFrame过长时会自动换行(print()显示方式)或自动省略(单元格最后一行直接显示),在一些情况下看上去不
- #!/usr/bin/env pythonimport sys,timefrom socket import socketdef read_
- 当浏览者进入你的网站首页时或提交某些表单时,会弹出网站声明或提交说明等文本信息框,引导浏览者使用你的网站。实现这个功能我们是用Dreamwe
- 一,通用的ASCII码对照表 图解ASCII码对照表图,以字符A为例Dec表示十进制,如65Hx表示十六进制,如41Oct表示八进制,如10
- 今天来和大家聊聊抽样的几种常用方法,以及在Python中是如何实现的。抽样是统计学、机器学习中非常重要,也是经常用到的方法,因为大多时候使用
- 如果你学过操作系统,那么对于锁应该不陌生。锁的含义是线程锁,可以用来指定某一个逻辑或者是资源同一时刻只能有一个线程访问。这个很好理解,就好像
- 本文实例讲述了Python使用django获取用户IP地址的方法。分享给大家供大家参考。具体如下:函数实现:def get_client_i
- 本文实例讲述了Python实现html转换为pdf报告(生成pdf报告)功能。分享给大家供大家参考,具体如下:1、先说下html转换为pdf
- 前言春节快到了,一年一度的支付宝集五福活动就要来了,阿牛也是突发奇想,看能不能用python的turtle库画个"福"字
- 字符串中字符大小写的变换1. str.lower() //小写>>> 'SkatE'