题解 | #迷宫问题#

# 定义一个用来在迷宫中找路径的函数
def bfs(maze):
    # 获取迷宫的行数和列数
    m, n = len(maze), len(maze[0])
    # 如果迷宫是空的，就没有路径
    if m == 0 or n == 0:
        return []
    # 准备一个队列，开始时只有起点在里面
    queue = [(0, 0, [(0, 0)])]
    # 记录我们访问过的地方，开始时只有起点
    visited = set([(0, 0)])

    # 当队列不为空时，继续寻找路径
    while queue:
        # 从队列中取出一个位置和到这个位置的路径
        row, col, path = queue.pop(0)
        # 如果这个位置是出口，就找到了路径
        if (row, col) == (m - 1, n - 1):
            return path
        # 尝试向上下左右四个方向移动
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            # 计算移动后的位置
            next_row, next_col = row + dx, col + dy
            # 如果新位置有效，并且没有被墙挡住，并且没有访问过
            if (
                0 <= next_row < m
                and 0 <= next_col < n
                and maze[next_row][next_col] == 0
                and (next_row, next_col) not in visited
            ):
                # 将新位置和到达新位置的路径加入队列
                queue.append((next_row, next_col, path + [(next_row, next_col)]))
                # 标记新位置为已访问
                visited.add((next_row, next_col))
    # 如果走遍了所有可能的路都没有找到出口，就返回空列表
    return []


# 不停地读取输入，直到没有更多数据
while True:
    try:
        # 读取迷宫的行数和列数
        m, n = map(int, input().split())
        maze = []
        # 根据行数读取迷宫数据
        for _ in range(m):
            row = list(map(int, input().split()))
            maze.append(row)

        # 使用BFS方法找路径
        path = bfs(maze)

        # 打印找到的路径
        for step in path:
            print(f"({step[0]},{step[1]})")
    # 如果读取数据时出错（例如没有更多数据了），就结束程序
    except EOFError:
        break