怎么用dfs深度优先搜索实现走迷宫呀,怎么实现两个坐标中走迷宫出一个路径
1条回答 默认 最新
关注
试着写了一下,应该还可以优化
def findpath(puzzle, start, end): d = [(-1,0),(0,1),(1,0),(0,-1)] vis = [[-1 for _ in range(len(puzzle[0]))] for _ in range(len(puzzle))] vis[start[0]][start[1]]=start dfs = [start] while dfs: x,y = dfs.pop() for i in range(4): m = x+d[i][0] n = y+d[i][1] if 0<=m<len(puzzle) and 0<=n<len(puzzle[0]) and puzzle[m][n]==0 and vis[m][n]==-1: dfs.append((x,y)) dfs.append((m,n)) vis[m][n]=(x,y) if end==(m,n):return dfs break return dfs puzzle = [ [0,0,0,0], [0,1,1,0], [0,0,1,1], [1,0,0,0] ] start = eval(input("请输入起始坐标(x,y):")) end = eval(input("请输入终点坐标(m,n):")) res = findpath(puzzle, start, end) if res:print(res) else: print('无路可走')
测试:
请输入起始坐标(x,y):(0,0) 请输入终点坐标(m,n):(3,3) [(0, 0), (1, 0), (2, 0), (2, 1), (3, 1), (3, 2), (3, 3)]
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 1无用