Python教程

python 迷宫求路(递归方法)

本文主要是介绍python 迷宫求路(递归方法),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

代码样本:

 

class MazeRoute:#  定义类MazeRoute
    def __init__(self,arr,m,n):#在类实例创建的时候自动会被执行。
        self.__arr = arr  # 定义私有类成员self.__arr二维列表作为迷宫
        self.__m = m    #  定义私有类成员self.__m为迷宫的深度
        self.__n = n     # 定义私有类成员self.__n为迷宫的长度
    def is_true(self, arr, y, x):  # 判断函数 判断当前路径是否合法
            if y > self.__n-1 or y < 0 or x > self.__m-1 or x < 0:  # 下一步是否合法
                return False  # 返回Flase
            elif arr[y][x] == -1 or arr[y][x] == 0 :
                return False
            else:
                return True  # 返回True
    def dfs(self, arr,lst, start_y, start_x,end_y,end_x):  # 递归深搜
            if start_y == self.__n - 1 and start_x == self.__m - 1:  # 如果当前坐标等于目标坐标
                lst.append((self.__n-1,self.__m-1))
                print(lst)
                return lst
            else:
                    self.__arr[start_y][start_x] = -1
                    lst.append((start_y, start_x))
                    for i in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
                        if self.is_true(arr, start_y + i[0], start_x + i[1]):
                                self.dfs(arr,lst, start_y + i[0], start_x + i[1],end_y,end_x)
                                lst.pop()
                                break
def find_route(arr,n,m):
        lst = []
        end_y  =m-1
        end_x = n-1
        a = MazeRoute(arr,n,m)
        return a.dfs(arr,lst,0,0,end_y,end_x)
if __name__ == '__main__':
    n,m = map(int,input().split())
    arr = [[1,0,0,0],[1,1,0,0],[0,1,1,1],[0,0,0,1]]
    lst = []
    find_route(arr,n,m)

输入样本:

 解释:分别输入迷宫的长和宽

输出样本:

 

这篇关于python 迷宫求路(递归方法)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!