题解 | #迷宫问题#

from collections import deque
def bfs(maze, vertex, end):
    # 起点初始化
    queue = deque([vertex])
    parent = {vertex: None}
    m, n = len(maze), len(maze[0])
    visit = [[False] * n for _ in range(m)]
    visit[vertex[1]][vertex[0]] = True
    dir = [[1, 0], [-1, 0], [0, 1], [0, -1]]  # 注：如果可以走斜线，则加上四个方向，[1,1],[1,-1],[-1,1],[-1,-1]

    # 开始遍历
    while queue:
        vertex = queue.popleft()

        if vertex == end:
            paths = deque()
            node = end
            while node:
                paths.appendleft(node)
                node = parent[node]
            min_steps = len(paths)
            return paths,min_steps

        x, y = vertex[0], vertex[1]  # 横坐标x，纵坐标y；x->列，y->行
        for i in range(4):
            nx, ny = x + dir[i][0], y + dir[i][1]
            if 0 <= nx < n and 0 <= ny < m and (not visit[ny][nx]) and maze[ny][nx] == 0:
                queue.append((nx, ny))
                parent[(nx, ny)] = vertex
                visit[ny][nx] = True

if __name__ == '__main__':
    m, n = [int(i) for i in input().split()]
    maze = [[int(i) for i in input().split()] for _ in range(m)]
    vertex = (0, 0)
    end = (n - 1, m - 1)

    paths,_ = bfs(maze, vertex, end)
    for t in paths:
        print(f'({t[1]},{t[0]})')