题解 | #迷宫问题#

import sys

n, m = input().strip().split()
maze = []

for line in sys.stdin:
    if line == "\n":
        break
    maze.append(line.strip().split())

# 每次向上下左右前进一格，递归就完事
# 使用 route 存储路径，注意使用 copy 深拷贝
def recursive(
    maze: list[str],
    route: list[tuple],
    i: int,
    j: int,
    n: int,
    m: int,
    res: list[tuple],
):
    if route and route[-1] == (n - 1, m - 1):
        return
    if (i, j) == (n - 1, m - 1):
        route.append((i, j))
        res.extend(route)
        return route
    if 0 <= i <= n - 1 and 0 <= j <= m - 1 and maze[i][j] != "1" and not res:
        route.append((i, j))
    if j - 1 >= 0 and maze[i][j - 1] != "1" and (i, j - 1) not in route and not res:
        recursive(maze, route.copy(), i, j - 1, n, m, res)
    if j + 1 <= m - 1 and maze[i][j + 1] != "1" and (i, j + 1) not in route and not res:
        recursive(maze, route.copy(), i, j + 1, n, m, res)
    if i - 1 >= 0 and maze[i - 1][j] != "1" and (i - 1, j) not in route and not res:
        recursive(maze, route.copy(), i - 1, j, n, m, res)
    if i + 1 <= n - 1 and maze[i + 1][j] != "1" and (i + 1, j) not in route and not res:
        recursive(maze, route.copy(), i + 1, j, n, m, res)


res = []
recursive(maze, [], 0, 0, int(n), int(m), res)

for r in res:
    print(f"({r[0]},{r[1]})")