用python实现迷宫寻路

好的，我可以帮你介绍一下 Python 实现迷宫寻路的方法。

首先，我们需要定义迷宫的结构。可以使用二维列表来表示迷宫，其中 0 表示可以通行的格子，1 表示障碍物或墙壁。例如：

maze = [
    [0, 0, 0, 0, 0, 0, 0, 1],
    [0, 1, 1, 0, 1, 1, 0, 1],
    [0, 0, 0, 1, 0, 0, 0, 1],
    [0, 1, 0, 0, 1, 1, 0, 0],
    [0, 1, 1, 1, 0, 0, 1, 1],
    [0, 1, 0, 0, 0, 1, 0, 1],
    [0, 0, 0, 1, 0, 0, 0, 1],
    [0, 1, 1, 1, 0, 1, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0]
]

其中，第一行和最后一行表示迷宫的边界，都是墙壁。我们假设起点是 (1, 1)，终点是 (7, 7)。

接着，我们可以使用广度优先搜索（BFS）算法来寻找从起点到终点的最短路径。BFS 需要借助一个队列来实现，每次从队列中取出一个格子，然后将其周围可以通行的格子加入队列中。为了记录每个格子是否已经被访问过，我们可以使用一个二维列表来表示。例如：

visited = [
    [False, False, False, False, False, False, False, True],
    [False, True, True, False, True, True, False, True],
    [False, False, False, True, False, False, False, True],
    [False, True, False, False, True, True, False, False],
    [False, True, True, True, False, False, True, True],
    [False, True, False, False, False, True, False, True],
    [False, False, False, True, False, False, False, True],
    [False, True, True, True, False, True, False, False],
    [False, False, False, False, False, False, False, False]
]

我们可以使用一个字典来记录每个格子的父节点，可以方便地回溯找到最短路径。例如：

parent = {
    (1, 1): None,
    (2, 1): (1, 1),
    (2, 2): (2, 1),
    (2, 3): (2, 2),
    ...
    (7, 6): (6, 6),
    (7, 7): (7, 6)
}

最后，我们可以使用一个函数来实现迷宫寻路的过程。例如：

from collections import deque

def find_path(maze, start, end):
    rows, cols = len(maze), len(maze[0])
    visited = [[False] * cols for _ in range(rows)]
    parent = {}

    queue = deque([start])
    visited[start[0]][start[1]] = True

    while queue:
        curr = queue.popleft()
        if curr == end:
            break
        x, y = curr
        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 maze[nx][ny] == 0 and not visited[nx][ny]:
                queue.append((nx, ny))
                visited[nx][ny] = True
                parent[(nx, ny)] = curr

    if end not in parent:
        return None

    path = []
    curr = end
    while curr != start:
        path.append(curr)
        curr = parent[curr]
    path.append(start)
    path.reverse()

    return path

这个函数接受三个参数：迷宫、起点和终点。它返回从起点到终点的最短路径。如果没有路径，返回 None。