时间戳

首页 > 解决方案 > Python Maze BFS 最短路径

python - Python Maze BFS 最短路径

问题描述

我正在学习搜索算法并尝试实现 BFS 算法以检查在给定起始位置的迷宫中是否可以达到目标。迷宫是从 txt 文件作为二维数组导入的。我的解决方案似乎找到了目标，但是我无法仅显示所采用的路径，我只能显示所有访问过的节点。我想在算法运行后用表示所走路径的标记来显示迷宫。当前显示用“。”访问的索引。象征。& 符号代表一堵无法通过的墙。这是我的代码：

def BFS(maze, start, goal):

queue = deque([start])

visited = set(([start]))

while(queue):

    x, y = queue.popleft()

    if ((x,y) == goal):
        return x

    if (start != (x,y)):
        maze[x][y] = '.'

    visited.add((x,y))

    if (maze[x][y+1] != "&" and (x,y+1) not in visited):
        queue.append((x,y+1))

    if (maze[x][y-1] != "&" and (x,y-1) not in visited):
        queue.append((x,y-1))

    if (maze[x-1][y] != "&" and (x-1,y) not in visited):
        queue.append((x-1,y)) 

    if (maze[x+1][y] != "&" and (x+1,y) not in visited):
        queue.append((x+1,y))

谢谢

标签： pythonalgorithmpathbreadth-first-searchmaze

解决方案

我能够弄清楚。我必须使用一个字典来存储每个被调用节点和调用它的节点。之后，一旦我达到目标，我就会遍历每个字典键值对，从我的目标开始作为找到我的路径的关键。

推荐阅读