题解 | #迷宫问题#
迷宫问题
https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc
path = ['(0,0)']
seen = []
steps = [-1, 1]
def dfs(l, c):
point = "(" + str(l) + "," + str(c) + ")"
# print(point)
seen.append(point)
if l == m - 1 and c == n - 1:
# reach the endpoint
for i in path:
print(i)
else:
for step in steps:
if 0 <= l + step <= m - 1 and maze[l + step][c] == 1:
# current point can't go
point = "(" + str(l + step) + "," + str(c) + ")"
seen.append(point)
elif 0 <= l + step <= m - 1 and maze[l + step][c] == 0:
point = "(" + str(l + step) + "," + str(c) + ")"
if point in seen:
# will not go back
pass
else:
path.append(point)
dfs(l + step, c)
path.pop()
if 0 <= c + step <= n - 1 and maze[l][c + step] == 1:
point = "(" + str(l) + "," + str(c + step) + ")"
seen.append(point)
elif 0 <= c + step <= n - 1 and maze[l][c + step] == 0:
point = "(" + str(l) + "," + str(c + step) + ")"
if point in seen:
# will not go back
pass
else:
path.append(point)
dfs(l, c + step)
path.pop()
m, n = list(map(int, input().split()))
maze = []
for _ in range(m):
maze.append(list(map(int, input().split())))
dfs(0,0)
