题解 | 迷宫问题

import sys
from collections import deque
r, c = map(int,input().split())
data = []
prev = [[None for _ in range(c)] for _ in range(r)]
for _ in range(r):
    data.append(list(map(int,input().split())))
q = deque()
q. append((0,0))
data[0][0] =1 
dirs = [(1,0),(0,1),(-1,0),(0,-1)]
while q:
    x, y = q.popleft()
    if x == r-1 and y == c-1:
        break
    for d in dirs:
        dx,dy = d[0],d[1]
        nx , ny = x+dx,y+dy
        if 0<=nx<r and 0<=ny<c and data[nx][ny] == 0:
            q.append((nx,ny))
            data[nx][ny] = 1
            prev[nx][ny] = (x, y)

# ---------------- 从终点倒推路径 ----------------
path = []
now = (r-1, c-1)
while now is not None:
    path.append(now)
    now = prev[now[0]][now[1]]

# 反转得到正序
path.reverse()

# ---------------- 输出路径 ----------------
for p in path:
    print(f"({p[0]},{p[1]})")