如何在Python中表示迷宫并实现含Gate的Start到End路径导航？

对新手来说，最直观的方式是用二维列表，用不同字符标记迷宫里的元素：

• 'S'：起点（Start）
• 'E'：终点（End）
• 'G'：关卡（Gate）
• '#'：墙（不可通行）
• '.'：可通行路径

举个示例：

maze = [
    ['S', '.', '#', 'G'],
    ['.', '#', '.', '.'],
    ['G', '.', '.', 'E']
]

每个列表元素对应迷宫的一个格子，maze[i][j]就代表第i行第j列的位置，非常容易理解。

这个需求本质是「从起点出发，遍历所有关卡后到达终点」，可以拆成3个简单步骤：

1. 先定位所有关键点（起点、所有关卡、终点）的坐标
2. 用BFS算法计算任意两个关键点之间的可行路径（BFS是迷宫找最短路径最适合的入门算法）
3. 枚举所有关卡的访问顺序，拼接出完整的可行路径

步骤1：提取关键点坐标 #

遍历迷宫，把所有关键位置的坐标存起来：

def find_key_points(maze):
    points = {'start': None, 'gates': [], 'end': None}
    for row_idx in range(len(maze)):
        for col_idx in range(len(maze[row_idx])):
            if maze[row_idx][col_idx] == 'S':
                points['start'] = (row_idx, col_idx)
            elif maze[row_idx][col_idx] == 'G':
                points['gates'].append((row_idx, col_idx))
            elif maze[row_idx][col_idx] == 'E':
                points['end'] = (row_idx, col_idx)
    return points

步骤2：BFS计算两点间的路径 #

写一个BFS函数，输入两个坐标，返回它们之间的可行路径（如果存在）：

def bfs(maze, start_pos, end_pos):
    rows = len(maze)
    cols = len(maze[0])
    # 四个移动方向：上、下、左、右
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    # 记录已访问的格子，避免走回头路
    visited = [[False for _ in range(cols)] for _ in range(rows)]
    # 队列里存（当前坐标，已走路径）
    queue = [(start_pos, [start_pos])]
    visited[start_pos[0]][start_pos[1]] = True
    
    while queue:
        current_pos, path = queue.pop(0)
        if current_pos == end_pos:
            return path
        # 尝试四个方向
        for dx, dy in directions:
            new_x = current_pos[0] + dx
            new_y = current_pos[1] + dy
            # 判断新位置是否合法（在迷宫范围内、没访问过、不是墙）
            if 0 <= new_x < rows and 0 <= new_y < cols:
                if not visited[new_x][new_y] and maze[new_x][new_y] != '#':
                    visited[new_x][new_y] = True
                    queue.append(((new_x, new_y), path + [(new_x, new_y)]))
    # 没有可行路径时返回空列表
    return []

步骤3：拼接完整路径（遍历所有关卡） #

用排列枚举所有关卡的访问顺序，依次拼接起点→关卡1→关卡2→…→终点的路径：

from itertools import permutations

def find_full_path(maze):
    points = find_key_points(maze)
    start = points['start']
    gates = points['gates']
    end = points['end']
    
    # 枚举所有关卡的访问顺序
    for gate_order in permutations(gates):
        full_path = []
        current_pos = start
        is_valid = True
        # 拼接起点到每个关卡的路径
        for gate in gate_order:
            segment = bfs(maze, current_pos, gate)
            if not segment:
                is_valid = False
                break
            # 拼接时去掉重复的起点（上一段的终点是下一段的起点）
            if full_path:
                full_path.extend(segment[1:])
            else:
                full_path = segment
            current_pos = gate
        # 拼接最后一个关卡到终点的路径
        if is_valid:
            end_segment = bfs(maze, current_pos, end)
            if end_segment:
                full_path.extend(end_segment[1:])
                return full_path
    # 所有顺序都尝试过，没有可行路径
    return []

测试示例 #

用之前的迷宫测试：

maze = [
    ['S', '.', '#', 'G'],
    ['.', '#', '.', '.'],
    ['G', '.', '.', 'E']
]

result = find_full_path(maze)
if result:
    print("找到可行路径：", result)
else:
    print("不存在符合要求的路径")

• 如果关卡数量超过6个，排列数会指数级增长（n!），回溯法效率会很低，这时候可以用动态规划优化，但入门阶段先掌握回溯法足够。
• 你也可以用数字代替字符标记迷宫（比如0=墙，1=路径，2=起点），原理完全一样。
• 可以把找到的路径标记回迷宫里，比如把路径上的格子改成'*'，方便可视化。

内容的提问来源于stack exchange，提问作者aakhilv