题解 | #迷宫问题#
https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc
#两个版本，一个DFS，一个回溯
#DFS
m, n = list(map(int, input().split()))
maze = []
for _ in range(m):
maze.append(list(map(int, input().split())))
def dfs(i,j,history):
maze[i][j]=1
if i==m-1 and j==n-1:
for item in history:
print('(' + str(item[0]) + ',' + str(item[1]) + ')')
return
directions=[(1,0),(-1,0),(0,1),(0,-1)]
for direction in directions:
ni,nj=i+direction[0],j+direction[1]
if 0<=ni<m and 0<=nj<n and maze[ni][nj]==0:
dfs(ni,nj,history+[(ni,nj)])
history=[(0,0)]
dfs(0,0,history)
#回溯
m, n = list(map(int, input().split()))
maze = []
for _ in range(m):
maze.append(list(map(int, input().split())))
def dfs(i,j):
if i==m-1 and j==n-1:
for item in history:
print('(' + str(item[0]) + ',' + str(item[1]) + ')')
return
directions=[(1,0),(-1,0),(0,1),(0,-1)]
for direction in directions:
ni,nj=i+direction[0],j+direction[1]
if 0<=ni<m and 0<=nj<n and maze[ni][nj]==0:
maze[ni][nj]=1
history.append((ni,nj))
dfs(ni,nj)
maze[ni][nj]=0
history.pop()
history=[(0,0)]
maze[0][0]=1
dfs(0,0)
