时间:2021-05-22
本文实例讲述了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 Truewalk(maze,3,3)递归是个好东西呀!
PS:本站还有一个无限迷宫游戏,基于JS实现,提供给大家参考一下:
在线迷宫小游戏:
http://tools.jb51.net/games/migong
更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
本文实例讲述了Python基于分水岭算法解决走迷宫游戏。分享给大家供大家参考,具体如下:#Solvingmazewithmorphologicaltransfo
递归算法是一种直接或者间接调用自身函数或者方法的算法。Java递归算法是基于Java语言实现的递归算法。递归算法的实质是把问题分解成规模缩小的同类问题的子问题,
本文实例讲述了Python解决走迷宫问题算法。分享给大家供大家参考,具体如下:问题:输入n*m的二维数组表示一个迷宫数字0表示障碍1表示能通行移动到相邻单元格用
本文实例讲述了基于C语言实现的迷宫算法。分享给大家供大家参考,具体如下:利用c语言实现迷宫算法,环境是vc++6.0.#include#include#incl
最近经常在机房看同学在玩一个走迷宫的游戏,比较有趣,自己也用java写一个实现随机生成迷宫的算法,其实就是一个图的深度优先遍历算法.基本思想就是,迷宫中的每个点