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,1],
    [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)
] # 四个方向
def maze_path(x1,y1,x2,y2):   # 起点位置和终点位置
    stack = []
    stack.append((x1,y1))  # (x1,y1)表示一个元组
    while(len(stack) > 0):
        curNode = stack[-1] # 当前的节点
        # x，y 四个方向 x-1,y;x+1,y;x,y-1;x,y+1
        if curNode[0] == x2 and curNode[1] == y2:
             # 走到终点了
            for p in stack:
                print(p)  # 输出路径坐标
            return True
        for dir in dirs:
            nextNode = dir(curNode[0],curNode[1])
             # 如果下一个节点能走
            if maze[nextNode[0]][nextNode[1]] == 0:
                stack.append(nextNode)  # 把路径加上
                maze[nextNode[0]][nextNode[1]] = 2  # 2表示为已经走过
                break
        else:
            maze[curNode[0]][curNode[1]] = 2
            stack.pop()  # 回退
    else:
        print("没有路")
        return False
maze_path(1,1,8,8)

2、队列——广度优先搜索

思路：从一个节点开始，寻找所有接下来能继续走的点，继续不断寻找，直到找到出口，使用队列存储当前正在考虑的节点

注意：找出来的一定是最短路径，因为是多方向同时进行，所以先返回的一定是最先到的，最短的

完整代码：

from collections import deque
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,1],
    [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)
]
def print_r(path):  # path是所有的路径，前两个元素是坐标，最后一个数是记录谁带他来
    curNode = path[-1]  # path的最后一个元素就是终点
    realpath = []  # 真正的路径
    while curNode[2] != -1:  # 等于-1是最开始
        realpath.append((curNode[0:2])) # 不需要第三个元素
        curNode = path[curNode[2]]  # curNode[2]这个位置上的数
    realpath.append(curNode[0:2])  # 把起点放进去
    realpath.reverse()   # reverse作用把列表自己倒序后变成自己
    for node in realpath:
        print(node)
def maze_path_queue(x1,y1,x2,y2):
    queue = deque()
    queue.append((x1,y1,-1))
    path = []
    while len(queue) > 0:
        curNode = queue.popleft()  # 队首出队
        path.append(curNode)
        if curNode[0] == x2 and curNode[1] == y2:
            # 终点
            print_r(path)
            return True
        for dir in dirs:
            nextNode = dir(curNode[0],curNode[1])
            if maze[nextNode[0]][nextNode[1]] == 0:
                queue.append((nextNode[0],nextNode[1],len(path) - 1 ))
                # nextNode是curNode带来的，所以返回的应该是curNode的下标，就是len(path)-1
                maze[nextNode[0]][nextNode[1]] = 2  # 标记为已经走过
    else:
        print("没有路")
        return False
maze_path_queue(1,1,8,8)