题解 | 迷宫问题

from collections import deque

def bfs(h, l, mg):
    # print(h)
    # print(l)
    # 定义方向
    # 左右 上下

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

    # 初始化层序队列 和访问标识
    q = deque()
    q.append((0, 0))
    visited = [[False] * (l) for _ in range(h)]
    visited[0][0] = True

    # 存储父节点 用于父节点回溯 通过 这个父节点 明确终点之后直接回溯
    parent = [[None] * l for _ in range(h)]

    while q.__len__() > 0:
        x, y = q.popleft()

        if x == h - 1 and y == l - 1:
            break

        for dx, dy in directions:
            # 某一个方向上预处理
            nx, ny = x + dx, y + dy
            # 访问判断 越界判断 墙体判断
            if 0 <= nx < h and 0 <= ny < l and mg[nx][ny] == 0 and not visited[nx][ny]:
                # 层序遍历的操作
                visited[nx][ny] = True
                q.append((nx, ny))
                parent[nx][ny] = (x, y)
    # 终点回溯
    px, py = (h - 1, l - 1)
    path = []
    path.append(f"({px},{py})")
    while parent[px][py] is not None:
        # 到达终点
        if px == 0 and py == 0:
            break
        #取当前节点的父节点
        px, py = parent[px][py]
        path.append(f"({px},{py})")

    # arr = path.reverse()
    
    end = len(path) -1
    while end>=0:
        print(path[end])
        end -=1
    # print(path)
    
mg=[]
a=input().split()
h=int(a[0])
l=int(a[1])

for i in range(h):
    cur = input().split()
    curarr=[]
    for j in cur:
        curarr.append(int(j))
    mg.append(curarr)


# print(mg)
bfs(h,l,mg)