题解 | 迷宫问题

其实可以有一个 n^4 的dp（真的能说是dp嘛,虽然确实是转移）,但是怀疑python过不去，还是老老实实dfs[doge]

h, w = list(map(int,input().split()))
mp = [list(map(int,input().split())) for i in range(h)]
mp[0][0] = 114514
dp = [[(-1,-1) for j in range(w)] for i in range(h)]

def dfs(x,y):
    for a,b in [(1,0),(0,1),(-1,0),(0,-1)]:
        nx = x + a
        ny = y + b
        if(0 <= nx < h and 0 <= ny < w) and not mp[nx][ny] and dp[nx][ny] == (-1,-1):
            dp[nx][ny] = (x,y)
            dfs(nx,ny)

dp[0][0] = (114514,114514)
dfs(0,0)
    
ans = []
pos = (h - 1,w - 1)
while pos != (0,0):
    ans.append(pos)
    pos = dp[pos[0]][pos[1]]
ans.append(pos)
ans.reverse()
for i in ans:
    print(f"({i[0]},{i[1]})")

#牛客春招刷题训练营# + 链接