使用队列解决迷宫问题（广度优先搜索 / 最短路径）

使用,队列,解决,迷宫,问题,广度,优先,搜索,路径 · 浏览次数 : 2

小编点评

**博客地址：** https://www.cnblogs.com/zylyehuo/# -*- coding: utf-8 -*- **程序简介：** 该程序提供了一种生成迷宫路径的方法。它使用队列算法和迷宫数据结构来找到从起点到终点的路径。 **程序步骤：** 1. **初始化迷宫：**创建一个包含迷宫数据的三维列表 `maze`。 2. **创建路径队列：**将起点和终点放入队列中，并设置其深度为 -1，表示未访问过。 3. **开始搜索路径：**从队列中取出第一个节点，将其加入路径中。 4. **扩展路径：**从当前节点的所有可访问的相邻节点中选择其中最安全的节点作为下一个节点。 5. **检查路径结束：**如果当前路径到终点，则打印路径并返回 True。 6. **处理已访问的节点：**标记已访问的节点，以便在搜索结束后进行清理。 7. **递归搜索：**如果当前节点不是终点，则扩展所有可访问的相邻节点，并将它们加入队列中。 **代码示例：** ```python 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] ] print_r(maze_path_queue(1, 1, 8, 8)) ``` **结果：** 该程序将输出以下路径： ``` [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] ``` **注意：** 该程序的复杂性与迷宫大小有关。对于更大的迷宫，搜索效率可能下降。

正文

博客地址：https://www.cnblogs.com/zylyehuo/

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


def print_r(path):
    real_path = []
    i = len(path) - 1
    while i >= 0:
        real_path.append(path[i][0:2])
        i = path[i][2]

    real_path.reverse()
    for node in real_path:
        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))  # 后续节点进队，记录哪个节点带他来的
                maze[nextNode[0]][nextNode[1]] = 2  # 标记为已经走过
    else:
        print("没有路")
        return False


maze_path_queue(1, 1, 8, 8)  # 起点坐标和终点坐标