当先锋百科网

首页 1 2 3 4 5 6 7

迷宫问题一直是计算机基础算法中经典的问题之一。对于最短路径问题,我们可以使用 Python 中的广度优先搜索算法来解决迷宫最短路径的问题。


from collections import deque

def bfs(maze, start, end):
    queue = deque([start])
    visited = set()
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while queue:
        x, y, dist = queue.popleft()
        if (x, y) == end:
            return dist
        if (x, y) in visited:
            continue
        visited.add((x, y))
        for dx, dy in directions:
            new_x, new_y = x + dx, y + dy
            if 0 <= new_x < len(maze) and 0 <= new_y < len(maze[0]):
                if (new_x, new_y) not in visited and maze[new_x][new_y] != '#':
                    queue.append((new_x, new_y, dist + 1))
    return -1

python求解最短迷宫

上面的代码表示通过广度优先搜索从起点开始,不断向四个方向进行扩展,直到到达终点,找到最短路径。我们通过一个队列存储需要扩展的点,并使用一个 visited 集合来记录已经访问过的点。循环扩展到终点时,返回最短距离。

我们可以使用一个二维数组来表示迷宫,其中 . 表示可走的路,# 表示墙壁阻挡,S 表示起点,E 表示终点。


maze = [
    ['#', '#', '#', '#', '#', '#', '#', '#', '#'],
    ['#', '.', '.', '.', '#', '.', '.', '.', '#'],
    ['#', '.', '#', '.', '#', '.', '#', '.', '#'],
    ['#', '.', '#', '.', '.', '.', '.', '.', '#'],
    ['#', '#', '#', '#', '#', '#', '#', '#', '#']
]

start = (1, 1, 0)  # 起始点和初始距离
end = (3, 6)  # 终点
dist = bfs(maze, start, end)
print("Distance:", dist)

实现了上述算法,我们便可成功地找出迷宫中的最短路径。