算法:Python递归实现走迷宫 |
您所在的位置:网站首页 › 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=0 and y |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |