1 问题
Python中如何用栈解决迷宫问题?
2 方法
3、不符合的则出栈,最后在栈里的则是路径
代码清单 1
##栈解决迷宫问题
##四个方向
dirs=[
lambda x,y:(x-1,y),
lambda x,y:(x,y+1),
lambda x,y:(x+1,y),
lambda x,y:(x,y-1)
]
def maze_find(l,x1,y1,x2,y2):
stack=[]##建立栈
stack.append((x1,y1))##建立元组记录坐标
while len(stack)>0:
now_node = stack[-1]
if now_node[0]==x2 and now_node[1]==y2:##到达终点
for path in stack:
print(path)
return True
for dir in dirs:##四个方向走
next_node=dir(now_node[0],now_node[1])
if l[next_node[0]][next_node[1]]==0:
stack.append(next_node)
l[next_node[0]][ next_node[1]] =2
break##找到一个就可以走
else:##四个方向都不可以走 出栈 寻找上一个顶点
l[now_node[0]][now_node[1]] =2
stack.pop()
else:##没有出路
print("世界上本来没有路,但是走的人多了便有了路!")
return False
if __name__ == '__main__':
##0表示可以走 1表示不可以走,为避免死循环一般将走过的方块置为-1,退栈之后将该方块重新置为0。
l=[
[1,1,1,1,1,1,1],
[1,0,0,0,0,0,1],
[1,0,0,0,1,1,1]
]
maze_find(l,1,2,2,3)
3 结语
针对如何用栈(stack)解决迷宫问题的问题,提出从起点开始按照顺序寻找路径,通过栈记录已经走过的路径。如果最后发现不通就返回上一步,换个方向继续寻找的方法,证明该方法是有效的。解决此问题方法了解之后还需注意一些细节问题,就如迷宫中 0 表示可以通过,1表示无法通过,-1 表示已经走过的路,左上角坐标为(0, 0),横轴为x 轴,纵轴为y 轴。迷宫四周必须用1围起来。写代码时要注意x,y不要混淆。