题解 | Python #走迷宫#

求最短路径用bfs
from collections import deque

dir = [(0, 1), (0, -1), (1, 0), (-1, 0)]

def bfs(maze,n,m,s,e):
    tag = [[False] * m for _ in range(n)]
    q = deque([(s[0], s[1], 0)])  # (x, y, steps)
    tag[s[0]][s[1]] = True

    while q:
        x, y, steps = q.popleft()
        
        # 如果当前点是终点，返回步数
        if (x, y) == e:
            return steps

        # 遍历四个方向
        for dx, dy in dir:
            nx, ny = x + dx, y + dy

            # 判断是否越界以及是否可以走
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] == '.' and not tag[nx][ny]:
                tag[nx][ny] = True
                q.append((nx, ny, steps + 1))

    # 如果队列为空仍未找到终点，返回 -1
    return -1

# 输入处理
n, m = map(int, input().split())
xs, ys, xt, yt = map(int, input().split())
maze = [input().strip() for _ in range(n)]

# 调整坐标为从 0 开始的索引
s = (xs - 1, ys - 1)
e = (xt - 1, yt - 1)

# 调用 bfs 查找最短路径
result = bfs(maze, n, m, s, e)
print(result)