数据结构子目录https://www.jianshu.com/p/a344fa483655

题

有一个二维数组，表示迷宫（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,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]
 ]

栈的解法

思路

在任意节点，我们可以进行当前节点的上下左右四个方向的试探。

    lambda x, y: (x+1, y), #下
    lambda x, y: (x-1, y), #上
    lambda x, y: (x, y-1), #左
    lambda x, y: (x, y+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 solve_maze(x1,y1,x2,y2):
    # 空栈，用来存储正确的道路
    stack = []
    # 把初始位置放入，开始行走
    stack.append((x1,y1))
    maze[x1][y1] = 2  # 2表示已经走过的路
    # 通过判断栈的长度来决定是否进行尝试
    while len(stack) > 0:
        # 取出栈顶
        cur_node = stack[-1]
        if cur_node == (x2,y2): #如果到终点了，输出栈的内容，返回True
            print(stack)
            return True
        # 遍历 移动 列表， 找到合适的移动，同时将已经走过的路添加到栈内，标注为 2 
        for i in dirs:
            next_node = i(*cur_node)
            # 看看当前节点的上下左右操作之后，那个方向可以前进。
            if maze[next_node[0]][next_node[1]] == 0:
                stack.append(next_node)
                maze[next_node[0]][next_node[1]] = 2
                break
        # 如果是死胡同，就去栈顶，重新选择道路。
        else:
            stack.pop()
    else:
        # 如果栈空了，就打印没有结果，返回false
        print("没有结果")
        return False

solve_maze(1,1,8,8)

队列的解法

思路

应用队列解决迷宫问题，叫做广度优先搜索。

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

示意图

解法

创建一个空队列，将起点1放入队列，然后1只有一条路可走，因此1出列2进列，到3入列后由于有两条路可走，3出列4、5入列；随后先走4的方向4出列6入列，再5出列7入列，此时6、7在队列中，6又有了两个方向，此时6出列，8、9入列，此时队列中为7\8\9，以此规律依次类推，直到找到出口。

队列中存的不再是路径，而是现在考虑的路，分岔的中端。因此输出路径会比较麻烦。

代码

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):
    """打印路径"""
    curNode = path[-1]    # 最后一个节点
    realpath = []         # 出去的路径
    while curNode[2] != -1:   # 判断最后一个节点的标记是否为-1，如果是-1说明是起始点，如果不是-1就继续查找
        realpath.append(curNode[0:2])   # 拿到并添加节点x,y坐标信息
        curNode = path[curNode[2]]      # 这里curNode[2]是当前节点的前一步节点的标识：path的下标，因此path[curNode[2]]拿到前一节点
 
    realpath.append(curNode[0:2])       # 在这里curNode[2] == -1，是迷宫起点，将坐标信息加入路径
 
    realpath.reverse()    # 将列表倒序，将前面生成的从后往前的列表变为从前往后
    print(realpath)
 
 
def maze_path_queue(x1, y1, x2, y2):   # (x1,y1)代表起点；(x2,y2)代表终点
    """用队列实现迷宫问题——深度优先搜索"""
    queue = deque()   # 创建队列
    queue.append((x1, y1, -1))    # 加入起点，第三个参数是记录时谁让它来的，这里起始点设置为-1
    path = []   # 保存出队节点
    while len(queue) > 0:   # 只有队不空就一直循环
        curNode = queue.pop()  # 队首节点出队，并存为当前节点变量
        path.append(curNode)   # 添加到path列表
        if curNode[0] == x2 and curNode[1] == y2:   # 判断是否找到终点
            print_r(path)   # 如果到达终点，打印路径
            return True
 
        for dir in dirs:    # 搜索四个方向
            nextNode = dir(curNode[0], curNode[1])    # curNode[0],curNode[1]分别是当前节点x、y
            if maze[nextNode[0]][nextNode[1]] == 0:   # 如果有路可走
                queue.append((nextNode[0], nextNode[1], len(path) - 1))   # 后续节点进队，标记谁让它来的：path最后一个元素的下标
                maze[nextNode[0]][nextNode[1]] = 2   # 设置为2，标记为已经走过
 
    else:   # 如果队列为空（当前节点到了死路，节点删除没有新节点加入），没有路
        print("没有路")
        return False
 
 
maze_path_queue(1,1,8,8)