python迷宫最短路径

解决迷宫最短路径问题的一种常用算法是广度优先搜索（BFS）。这里简单介绍一下BFS的思路。

BFS的基本思路是从起点开始，一层一层地向外扩展，直到找到终点为止。在扩展过程中，需要记录每个节点的父节点，以便在找到终点后回溯路径。

以下是一个简单的Python实现：

from collections import deque

def bfs(maze, start, end):
    rows, cols = len(maze), len(maze[0])
    visited = [[False] * cols for _ in range(rows)]
    queue = deque([(start[0], start[1], 0, None)])  # (x, y, steps, parent)

    while queue:
        x, y, steps, parent = queue.popleft()
        if (x, y) == end:
            path = [(x, y)]
            while parent:
                x, y, _, parent = parent
                path.append((x, y))
            return path[::-1], steps

        for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < rows and 0 <= ny < cols and not visited[nx][ny] and maze[nx][ny] == 0:
                visited[nx][ny] = True
                queue.append((nx, ny, steps + 1, (x, y, steps, parent)))

    return None, -1  # 没有找到路径

# 示例用法
maze = [
    [0, 0, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 0],
]
start = (0, 0)
end = (4, 4)
path, steps = bfs(maze, start, end)
print(path)
print(steps)

这个实现中，`maze`是一个二维数组表示迷宫，0表示可通过的格子，1表示障碍物。`start`和`end`分别是起点和终点的坐标。

函数返回一个元组，第一个元素是一个列表，表示从起点到终点的路径；第二个元素是一个整数，表示路径长度。如果没有找到路径，则返回`(None, -1)`。

在实现中，我们使用了一个队列来存储待扩展的节点。每个节点包含了当前节点的坐标、到达该节点的步数、以及父节点的信息（即上一个节点的坐标、步数和父节点）。在扩展节点时，我们先判断该节点是否为终点；如果不是，就按照上、右、下、左的顺序扩展周围的节点，并将它们加入队列。在加入队列前，需要判断该节点是否越界、是否已经访问过、是否为障碍物。如果符合条件，就将该节点标记为已访问，并加入队列。

在找到终点后，我们可以通过父节点信息回溯整个路径。