思路分析

本题迷宫只有一条通道，可以使用DFS，栈内元素正好为所走的路径，也是最短路径。

若迷宫不只一条通道，使用DFS走通的路径不一定是最短路径，最好采用BFS。

方法一：DFS

def DFS(start):
    stack = []
    stack.append(start)
    maze[0][0] = 2  # 走过标记为2
    while stack:
        if stack[-1] == end:  # 栈内元素为所走的路径
            for i in stack:
                print(f"({i[0]},{i[1]})")
            break
        r, c = stack[-1]
        neighbors = [(r - 1, c), (r, c + 1), (r + 1, c), (r, c - 1)]  # （r,c）的邻居
        for neighbor in neighbors:
            i, j = neighbor
            if 0 <= i < N and 0 <= j < M:  # 有效邻居
                if maze[i][j] == 0:
                    stack.append((i, j))
                    maze[i][j] = 2  # 走过标记为2
                    break
        else:  # 无路可走，回退
            stack.pop()

# 0.输入
N, M = map(int, input().split())
maze = [list(map(int, input().split())) for _ in range(N)]
# 1.起点与终点
start = (0, 0)
end = (N-1, M-1)
# 2.DFS
DFS(start)

方法二：BFS

def BFS(start):
    queue = []
    queue.append(start)
    visited = set()
    visited.add(start)
    father[(0, 0)] = (-1, -1)  # 任取（0，0）上一步（-1，-1）
    while queue:
        (r, c) = queue.pop(0)
        if (r, c) == end:
            return
        for i, j in [(r - 1, c), (r, c + 1), (r + 1, c), (r, c - 1)]:
            if 0 <= i < N and 0 <= j < M:
                if maze[i][j] == 0 and (i, j) not in visited:
                    queue.append((i, j))
                    visited.add((i, j))
                    father[(i, j)] = (r, c)

# 0.输入
N, M = map(int, input().split())
maze = [list(map(int, input().split())) for _ in range(N)]
# 1.起点与终点
start = (0, 0)
end = (N-1, M-1)
# 2.BFS后得出路径坐标的映射关系
father = {}  # 收集坐标与上一步映射关系，用字典来表示
BFS(start)
# 3.路径倒推
path = []
while end != (-1, -1):
    path.append(end)
    end = father[end]
for p in path[::-1]:  # 路径的逆序，按格式输出
    print(f"({p[0]},{p[1]})")