1 问题描述

1.1 任务描述

迷宫中从入口到出口的路径，有三种路径寻找要求： 1） 找到一条从入口到出口的路径 2） 找到从入口到出口的最短路径 3） 找到从入口到出口的所有路径（选做） 在没有学习使用图结构和图算法来解决此问题时，可以借助栈和队列对路径 进行穷举求解。分别使用顺序存储的线性表和链式存储的线性表来模拟上述约瑟夫问题。

1.2 输入描述

a) 先输入两个大于0的整数，用于表示迷宫的行和列的数目，即MN的迷宫（为降低输入迷宫数据的复杂度，可自行规定M和N的最大值）。 b) 再输入MN个整数，按行输入，每个输入数是0（表示通道）或者1（表示墙），用于构成M*N的迷宫。 c) 再输入迷宫入口点的两个整数，以行和列的方式构成。 d) 最后输入迷宫出口点的两个整数，以行和列的方式构成。

1.3 输出描述

a) 如果没有从入口到出口的路径，输出结果信息表示无法找到路径，程序结束。 b) 如果有从入口到出口的路径： i. 输出采用深度优先搜索发现的1条路径，输出结果要求包括路径中每个通道点的坐标、这个通道向下一个通道移动的方向（方向需要用可读的字符，如中文或其他文字）。如 （1，1）向南移动到达（2，1）。。 ii. 输出用广度优先搜索发现的最短路径，输出结果要求同上。 iii. 输出所有路径，输出时对路径编号，按路径从短到长依次输出。输出结果要求同上。

1.4 程序功能

在一个给定了起点和终点的无环迷宫中，程序分别输出一条通过深度优先搜索发现的可行路径和一条通过广度优先搜索发现的最短路径。 并在广度优先搜索中完成输出所有路径，输出时对路径编号，按路径从短到长依 次输出。