题解 | #迷宫问题#

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

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

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


N, M = map(int, input().split())
maze = [list(map(int, input().split())) for _ in range(N)]
start = (0, 0)
end = (N - 1, M - 1)
DFS(start, end)