python 迷宫求路(递归方法)
2021/7/29 17:11:07
本文主要是介绍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 迷宫求路(递归方法)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-25Python编程基础:变量与类型
- 2024-11-25Python编程基础与实践
- 2024-11-24Python编程基础详解
- 2024-11-21Python编程基础教程
- 2024-11-20Python编程基础与实践
- 2024-11-20Python编程基础与高级应用
- 2024-11-19Python 基础编程教程
- 2024-11-19Python基础入门教程
- 2024-11-17在FastAPI项目中添加一个生产级别的数据库——本地环境搭建指南
- 2024-11-16`PyMuPDF4LLM`:提取PDF数据的神器