Nancy - 栈和队列的应用—

给一个二维列表，表示迷宫（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]
]

栈——深度优先搜索

回溯法
思路：从一个节点开始，任意找下一个能走的路，当找不到能走的点时，退回上一个点寻找是否有其他方向的点。
使用栈存储当前路径

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, y + 1),
    lambda x, y: (x + 1, y),
    lambda x, y: (x, y - 1),
]


def maze_path(x1, y1, x2, y2):
    """
    :param x1: 起点（表示第几行）
    :param y1: 起点（表示第几列）
    :param x2: 终点（表示第几行）
    :param y2: 终点（表示第几列）
    :return:
    """
    stack = []
    stack.append((x1, y1))
    while len(stack) > 0:
        curNode = stack[-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[nextNode[0]][nextNode[1]] = 2  # 当四个方向都不能走的时候，脚下的点还是要标记
            stack.pop()
    else:
        print("没有出路")
        return False


maze_path(1, 1, 8, 8)

队列——广度优先搜索

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

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, y + 1),
    lambda x, y: (x + 1, y),
    lambda x, y: (x, y - 1),
]


def print_r(path):
    curNode = path[-1]
    realPath = []
    while curNode[2] != -1:
        realPath.append((curNode[0], curNode[1]))
        curNode = path[curNode[2]]

    realPath.append((curNode[0], curNode[1]))  # 加入起点
    realPath.reverse()
    for node in realPath:
        print(node)


def maze_path(x1, y1, x2, y2):
    """
    :param x1: 起点（表示第几行）
    :param y1: 起点（表示第几列）
    :param x2: 终点（表示第几行）
    :param y2: 终点（表示第几列）
    :return:
    """
    queue = deque()
    queue.append((x1, y1, -1))
    path = []  # 走过的所有路径
    while len(queue) > 0:
        curNode = queue.pop()
        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))  # 后续所有节点进队，记录从哪个节点过来的
                maze[nextNode[0]][nextNode[1]] = 2
    else:
        print("没有路了")
        return False


maze_path(1, 1, 8, 8)

您现在的位置是：网站首页>>算法与数据结构

栈和队列的应用——迷宫问题

栈——深度优先搜索

队列——广度优先搜索