|
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不要混淆。
|
