当前位置：首页 > 资讯 > 技术文档

Python基于递归算法实现的走迷宫问题

时间：2021-07-10 21:44 编辑：来源：阅读：
扫一扫，手机访问

摘要：Python基于递归算法实现的走迷宫问题

本文实例讲述了Python基于递归算法实现的走迷宫问题。分享给大家供大家参考，具体如下： [b]什么是递归?[/b] 简单地理解就是函数调用自身的过程就称之为递归。 [b]什么时候用到递归？[/b] 如果一个问题可以表示为更小规模的迭代运算，就可以使用递归算法。迷宫问题：一个由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)

递归是个好东西呀！ [b]PS：本站还有一个无限迷宫游戏，基于JS实现，提供给大家参考一下：[/b] [b]在线迷宫小游戏： [/b][url=http://tools.jb51.net/games/migong]http://tools.jb51.net/games/migong[/url] 更多关于Python相关内容感兴趣的读者可查看本站专题：《[url=http://www.1sucai.cn/Special/663.htm]Python数据结构与算法教程[/url]》、《[url=http://www.1sucai.cn/Special/642.htm]Python函数使用技巧总结[/url]》、《[url=http://www.1sucai.cn/Special/636.htm]Python字符串操作技巧汇总[/url]》及《[url=http://www.1sucai.cn/Special/520.htm]Python入门与进阶经典教程[/url]》希望本文所述对大家Python程序设计有所帮助。

全部评论(0)

上一篇：python安装与使用redis的方法
下一篇：Python实现数据库并行读取和写入实例

资讯排行榜
更多>>