迷宫求解之数据结构.doc

简介：
本文档探讨了利用不同数据结构（如栈、队列和图）解决迷宫问题的方法，并分析了每种方法的效率与适用性。 【完成题目3】迷宫求解 **问题描述** 以一个m*n的长方阵表示迷宫，0和1分别代表通路和障碍。设计程序对任意设定的迷宫求出一条从入口到出口的路径或得出没有可行路径的结论。 **基本要求** 首先实现栈类型，然后编写非递归程序来解决迷宫问题。找到的路径以三元组(i, j, d)的形式输出，其中 (i,j) 表示坐标位置，d表示移动方向。 **算法设计** 本实验的目标是设计一个程序，用于手动或自动生成n×m矩阵形式的迷宫，并寻找从入口到出口的一条通路。简化后的具体任务如下： 选择手动或者自动方式生成一个n×m大小的迷宫，将左上角设为入口点，右下角作为出口点。“0”表示可通行，“1”代表障碍物（即不可穿越）。假设从起点出发，目标是到达终点，并且可以向“上、下、左、右、左上、左下、右上和右下”八个方向移动。如果迷宫存在可行路径，则用特定符号分别表示0或1以及行走路线；输出原始的迷宫图及经过改造后的路径图，同时显示具体的行进路线。 若迷宫无法通行（即死路），则程序应给出相应的提示信息。 使用二维数组来存储迷宫数据。用户指定入口和出口的位置坐标，并且为了方便处理，在整个迷宫周围添加一圈障碍物。