题解 | #迷宫问题#
迷宫问题
http://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc
由于题目表明只有一条最优路径，则利用栈的思想，后进先出，这种方式不一定是最优路径
如果题目要求存在多个路径求最优，此法不通
# 定义一个数组 用于移动方向
dirs = [ lambda x,y:(x+1,y),
lambda x,y:(x-1,y),
lambda x,y:(x,y-1),
lambda x,y:(x,y+1),
]
def maze_path(n,m,maze):
# 定义栈
stack = []
# 保存初始值进栈
stack.append((0,0))
while len(stack) > 0 :
# 标记当前节点
curNode = stack[-1]
# 判断当前节点是否为终点
if curNode[0] == n-1 and curNode[1] == m-1 :
# 输出栈里的元组，就是行走路径
for i in stack:
print(f'({i[0]},{i[1]})')
return True
for dir in dirs :
# 计算出下一个节点的坐标
nextNode = dir(curNode[0],curNode[1])
# 避免数组越界，给定范围
if 0 <= nextNode[0] <= n-1 and 0 <= nextNode[1] <= m-1 :
# 如果下一个节点能通行的坐标位置是 0
if maze[nextNode[0]][nextNode[1]] == 0 :
# 添加到栈
stack.append(nextNode)
# 并标记已走过的路
maze[nextNode[0]][nextNode[1]] = 2
break
else : # 如果不是 0 则出栈
# 避免数组越界，给定范围
if 0 <= nextNode[0] <= n-1 and 0 <= nextNode[1] <= m-1 :
maze[nextNode[0]][nextNode[1]] = 2
stack.pop()
else:
return False
n,m = map(int,input().strip().split())
maze = [list(map(int,input().strip().split())) for _ in range(n)]
maze_path(n,m,maze)
投递淘天集团等公司10个岗位 >
