题解 | #迷宫问题#

from collections import deque


def main(maze):
    directions = [[1, 0], [-1, 0], [0, -1], [0, 1]]
    length = len(maze)
    width = len(maze[0])
    visited = [[0 for _ in range(width)] for _ in range(length)]
    step = [[(-1, -1) for _ in range(width)] for _ in range(length)]
    queue = deque([(0, 0)])
    visited[0][0] = 1
    result = []
    while queue:
        x, y = queue.popleft()
        if x == length - 1 and y == width - 1:
            break
        for d in directions:
            x1 = x + d[0]
            y1 = y + d[1]
            if x1 < 0 or y1 < 0 or x1 >= length or y1 >= width or \
                    visited[x1][y1] == 1 or maze[x1][y1] == 1:
                continue
            step[x1][y1] = (x, y)
            visited[x1][y1] = 1
            queue.append((x1, y1))

    if step[length - 1][width - 1] == (-1, -1):
        return False

    # 为了将路径保存在result列表中，需要在step数组中从出口向入口逆向查找
    re_x = length - 1
    re_y = width - 1
    result.append((re_x, re_y))
    while re_x or re_y:
        re_x, re_y = step[re_x][re_y]
        result.append((re_x, re_y))
    for i in result[::-1]:
        x, y = i
        print(f'({x},{y})')


while True:
    try:
        n, m = map(int, input().split())
        matrix = []
        for _ in range(n):
            matrix.append(list(map(int, input().split())))
        main(matrix)
    except:
        break