题解 | 迷宫问题

# ======================================
# 题目：迷宫寻路（单一路径，DFS+回溯模板）
# ======================================

# --------------------------
# 1. 读入迷宫数据
# --------------------------
h, w = map(int, input().split())  # h行，w列
grid = []
for _ in range(h):
    # 读入每一行的迷宫数据，0表示可走，1表示墙
    row = list(map(int, input().split()))
    grid.append(row)

# --------------------------
# 2. 初始化需要用到的变量
# --------------------------
# 记录路径的列表，用来存走过的坐标，最后直接输出
path = []
# 记录哪些格子已经走过，避免走回头路（死循环）
visited = [[False for _ in range(w)] for _ in range(h)]
# 四个方向：上、下、左、右（对应坐标变化）
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]


# --------------------------
# 3. 核心：DFS递归函数（带回溯）
# 参数：当前位置坐标 (x, y)
# 返回值：bool，表示从当前位置出发，能否走到终点
# --------------------------
def dfs(x, y):
    # 第一步：把当前坐标加入路径
    path.append((x, y))

    # 第二步：判断是否已经到达终点
    # 终点坐标是 (h-1, w-1)，因为题目里说起点是(0,0)，终点是最后一格
    if x == h - 1 and y == w - 1:
        return True  # 找到终点了，返回True，让上层知道路通了

    # 第三步：标记当前格子为已访问，避免回头走
    visited[x][y] = True

    # 第四步：依次尝试四个方向
    for dx, dy in directions:
        # 计算新的坐标
        nx = x + dx
        ny = y + dy

        # 判断新坐标是否合法（不越界、不是墙、没走过）
        # 条件1：nx在 0~h-1 之间，ny在 0~w-1 之间（不越界）
        # 条件2：grid[nx][ny] == 0（不是墙，可以走）
        # 条件3：visited[nx][ny] == False（没走过，不是回头路）
        if 0 <= nx < h and 0 <= ny < w and grid[nx][ny] == 0 and not visited[nx][ny]:
            # 递归调用DFS，从新坐标继续走
            if dfs(nx, ny):
                return True  # 只要有一个方向能走通，就直接返回True，不再试其他方向

    # 第五步：四个方向都走不通，回溯！
    # 把当前坐标从路径里删掉（相当于“退回去”）
    path.pop()
    return False  # 告诉上层：这个方向走不通，换别的路试试


# --------------------------
# 4. 主程序：调用DFS，然后输出路径
# --------------------------
# 从起点(0,0)开始走
dfs(0, 0)

# 按题目要求，输出路径上的每个坐标
for x, y in path:
    print(f"({x},{y})")