深度优先搜索怎么实现走迷宫呀

Question

怎么用dfs深度优先搜索实现走迷宫呀,怎么实现两个坐标中走迷宫出一个路径

Answer 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)]