数据结构迷宫最短路径

迷宫最短路径问题是一个经典的图论问题，可以使用广度优先搜索（BFS）算法来解决。下面是一个使用BFS算法求解迷宫最短路径的示例代码：

from collections import deque

def shortest_path(maze, start, end):
    # 定义四个方向的移动向量
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    rows, cols = len(maze), len(maze[0])
    queue = deque([(start, 0)])  # 使用队列保存当前位置和步数
    visited = set([start])  # 使用集合保存已经访问过的位置

    while queue:
        (x, y), steps = queue.popleft()
        if (x, y) == end:
            return steps  # 找到终点，返回步数

        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < rows and 0 <= ny < cols and maze[nx][ny] != '#' and (nx, ny) not in visited:
                queue.append(((nx, ny), steps + 1))
                visited.add((nx, ny))

    return -1  # 如果无法到达终点，返回-1

# 示例迷宫
maze = [
    ['#', '#', '#', '#', '#', '#', '#', '#'],
    ['#', '.', '.', '.', '#', '.', '.', '#'],
    ['#', '.', '#', '.', '#', '.', '#', '#'],
    ['#', '.', '#', '.', '.', '.', '.', '#'],
    ['#', '#', '#', '#', '#', '#', '#', '#']
]

start = (1, 1)  # 起点坐标
end = (3, 6)  # 终点坐标

min_steps = shortest_path(maze, start, end)
print("最短路径的步数为:", min_steps)