基于深度优先遍历

def solve(nx: int, ny: int, maze: list):
    visited = []
    directions = (
        (1, 0),
        (-1, 0),
        (0, 1),
        (0, -1)
    )

    def check(i, j):
        """
        计算能否从maze[i][j]通往终点
        """
        if i == nx - 1 and j == ny - 1:
            visited.append((i, j))
            return True
        else:
            res = False
            visited.append((i, j))
            for dx, dy in directions:
                new_i, new_j = i + dx, j + dy
                if 0 <= new_i < nx and 0 <= new_j < ny:
                    if (new_i, new_j) not in visited:
                        if maze[new_i][new_j] == 0:
                            res = check(new_i, new_j)
                            if res:
                                break
            if res:
                return True
            else:
                # 如果遇到无法继续前进情况，回退
                visited.pop()
                return False

    check(0, 0)
    for item in visited:
        print(f"({item[0]},{item[1]})")

nx, ny = list(map(int, input().split()))
maze = []
for i in range(nx):
    maze.append(list(map(int, input().split())))

solve(nx, ny, maze)