深度优先搜索

将迷宫表示为如下矩阵，1表示此路不通，0表示可行，起始位置A为迷宫的 [1][1] 位置，终点S为[8][8]，求一条从A到S的通路。

思路：

1. 构建四个方向–上下左右，将路径的每个节点都入栈，且当前节点将从四个方向探索，如果当前节点三路都不通将退栈返回上一节点。
2. 因为这里要输出路径，还应注意的一点是需要建立一个列表储存每个可行节点之间的连接，即路径。

#定义栈
class Stack:def __init__(self):self.data = []def __len__(self):return len(self.data)def push(self,e):self.data.append(e)def pop(self):if self.is_empty():return Noneelse:return self.data.pop()def is_empty(self):return  len(self.data) == 0def top(self):if self.is_empty():return Noneelse:return self.data[-1]def get(self):return self.data.pop(0)#迷宫矩阵 0表示可行 1表示不可行
maze = 
[[1,1,1,1,1,1,1,1,1,1],
[1,0,0,1,0,0,0,1,0,1],
[1,0,0,1,0,0,0,1,0,0],
[1,0,0,0,0,1,1,0,0,1],
[1,0,1,1,1,0,0,0,0,1],
[1,0,0,0,1,0,0,0,0,1],
[1,0,1,0,0,0,1,0,0,1],
[1,0,1,1,1,0,1,1,0,1],
[1,1,0,0,0,0,0,0,0,1],
[1,1,1,1,1,1,1,1,1,1]]#规定路径方向,依次为上下左右
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)]#x1,y1,x2,y2分别代表起点与终点在矩阵中的横纵坐标
def maze_path(x1,y1,x2,y2):temp_stack = Stack()# 起点入栈 注意需要以（x,y)形式保存，这样对应后面的路径temp_stack.push((x1,y1))while len(temp_stack)>0:#判定条件就是考虑迷宫根本走不通的情况：如果尝试了所有的点都不可行 那么最后一步肯定是起点出栈 进而栈空curNode = temp_stack.top() #当前节点必须是栈顶元素#走出迷宫：也就是下一节点是终点坐标if curNode[0] == x2 and curNode[1] == y2:while len(temp_stack)>0:print(temp_stack.get())breakfor dir in dirs:# 获取栈顶元素之后需要对其判断四条路哪条路可以走,就是判定其下一节点对应在矩阵上的值是否为0nextNode = dir(curNode[0],curNode[1])if maze[nextNode[0]][nextNode[1]] == 0:# 满足条件就要把下一节点入栈,入栈之后下一步肯定是走nextNode,所以同时要把该节点记录为已走过，不然如果此路不通退栈到上一节点时会重复走这条路temp_stack.push(nextNode)maze[nextNode[0]][nextNode[1]] = 2 #把走过的记录为2break #这里必须要跳出，因为循环里我们是在四个方向找路，所以只要一个方向出现可行的路就停止循环即可#写到这里发现忽略了走出迷宫的情况 所以添加到上面else:#这个else表示当前节点的四个方向我都没找到可行的出路，这时就要返回上一个点 并且删除栈顶元素maze[curNode[0]][curNode[1]] = 2 #当前节点五路可走时，退栈之前也要把它记为2，表示走过temp_stack.pop()else:  #这个else对应的是while的情况，如果栈为空还没找到，也就是表示走不出迷宫print("No way")return Falsemaze_path(1,1,8,8)	

#output
(1, 1)
(2, 1)
(3, 1)
(4, 1)
(5, 1)
(5, 2)
(5, 3)
(6, 3)
(6, 4)
(6, 5)
(7, 5)
(8, 5)
(8, 6)
(8, 7)
(8, 8)

我觉得相对于递归，用栈解决迷宫问题更好理解，这里仅供自己复习使用，也欢迎批评指正。