栈和队列的应用（迷宫问题）的代码实现（python语言）

向右看齐 2022-05-24 12:09 146阅读 0赞

*  迷宫问题描述：

> 给定一个迷宫，包括一个迷宫图，一个入口点和一个出口点  
> 设法找到一条从入口到出口的路径

def find_path(maze, start, end):  # 主函数
        mark(maez, start)
        if start == end:  # 如果已经到达出口
            print(start, end="")  # 输出这个位置
            return True  # 成功到达
        for i in range(4):  # 否则按四个方向顺序探查
            nextp = start[0] + dirs[i][0], start[1] + dirs[i][1]  # 下一个考虑
            if passable(maze, nextp):  # 不可行的相邻位置不管
                if find_path(maze, nextp, end):  # 如果从nextp可到达出口
                    print(start, end="")  # 输出这个点
                    return True  # 成功到达
        return False  # 失败
    
    
    def maze_solver(maze, start, end):
        if start == end:
            print(start)
            return
        st = ContinuityStack()
        mark(maze, start)
        st.push((start, o))  # 入口和方向0的序对入栈
        while not st.is_empty():  # 走不通时回退
            pos, nxt = st.pop()  # 取栈顶及其勘察方向
            for i in range(nxt, 4):  # 依次检查勘察方向
                nextp = (pos[0] = dir[i][0], pos[1] + dir[i][1])  # 算出下一点
                if nextp == end:  # 到达出口，打印路径
                    print_path(end, pos, st)
                    return
                if passable(maze, nextp):  # 遇到为勘察的新位置
                    st.push((pos, i+1))  # 原位置和下一方向入栈
                    mark(maze, nextp)
                    st.push((nextp, 0))  # 新位置入栈
                    break  # 退出内层循环，下次迭代将以新栈顶为当前位置继续
        print("No path found")  # 找不到路径