使用栈解决迷宫问题（深度优先搜索 / 回溯法）

使用,解决,迷宫,问题,深度,优先,搜索,回溯 · 浏览次数 : 5

小编点评

**博客地址：**`https://www.cnblogs.com/zylyehuo/# -*- coding: utf-8 -*-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)]** **函数 `maze_path` 的功能：** - 接受两个坐标 `(x1, y1)` 和 `(x2, y2)`，表示要找到的路径的起点和终点坐标。 - 使用 Stack 存储搜索的节点，并从堆中获取当前节点。 - 循环检查周围四个方向的节点，如果节点能走且尚未被访问过，将其加入堆中并标记为已访问。 - 如果找到终点坐标，则回溯所有从起点开始的节点，并打印所有路径。 - 如果未找到路径，则打印“没有路”。 **示例用法：** `maze_path(1, 1, 8, 8)` 这将返回一个包含路径的列表，例如： ``` [(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (2, 1), (2, 2), (2, 3), (2, 4)] ```

正文

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

# -*- coding: utf-8 -*-

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))
    while (len(stack) > 0):
        curNode = stack[-1]  # 当前的节点
        if curNode[0] == x2 and curNode[1] == y2:
            # 走到终点了
            for p in stack:
                print(p)
            return True

        # x,y 四个方向 x-1,y; x+1,y; x,y-1; x,y+1
        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)  # 起点坐标和终点坐标