8 顺序栈ADT模板简单应用算法设计：迷宫问题
作者: 冯向阳时间限制: 1S章节: DS:栈
截止日期: 2020-12-27 23:55:00
问题描述 :
目的：使用C++模板设计顺序栈的抽象数据类型（ADT）。并在此基础上，使用顺序栈ADT的基本操作，设计并实现简单应用的算法设计。
内容：（1）请参照顺序表的ADT模板，设计顺序栈的抽象数据类型。（由于该环境目前仅支持单文件的编译，故将所有内容都集中在一个源文件内。在实际的设计中，推荐将抽象类及对应的派生类分别放在单独的头文件中。参考教材、课件，以及网盘中的顺序表ADT原型文件，自行设计顺序栈的ADT。）
（2）ADT的简单应用：使用该ADT设计并实现若干应用顺序栈的算法设计。
应用：在迷宫中找出从入口到出口的路径是一个经典的程序设计问题。最简单的迷宫可以表示为一个由方块组成的矩阵，其中每个方块或为墙，或为通道。要求应用顺序栈，设计一个算法，在给定的迷宫矩阵maze中，找出从入口到出口的一条简单路径，即同一个通道在路径上不能出现两次以上。迷宫在计算机内可以用一个二维数组表示，每个数组元素表示一个方块。如果是通道，值为0，反之为1。
提示：
（1）可以用如图所示的方块表示迷宫。其中，图中的空白方块为通道；图中的斜线方块为墙；所求路径必须是简单路径，即在求得的路径上不能重复出现同一通道块。
(a) 迷宫的图形表示 (b) 迷宫的二维数组表示
（2）算法的基本思想为：
1）探索到出口的路径，具有递归性质：
若当前位置是出口，则问题已解决；
若当前位置不可通，则探索失败；
向可行的方向走一步，从那里出发探索到出口的路径。
2）本问题的特点：
在每个位置上可能有多个可行选择，有分支，需要逐一试探；
只需要找到一条路经(而不是所有可能路径)。
3）要解决这个问题，需要：
为问题找一种数据表示；
一种确定可行方向的方式；
防止出现兜圈子的情况(设法纪录已试探过的位置)。
（3）问题表示：
1）用整数矩阵(二维数组)表示迷宫。
2）初始时，通路上的点用0表示，非通路点用1。
3）入口和出口都是数组下标对。
4）为避免陷入无限循环，在探索中把试探过的点标记为2。
（4）方向处理：
1）找一种方便形式，表示从一个位置出发的可能探索位置。
迷宫中任一位置(i,j)有4个可能方向。
2）用数组direction表示可能方向(4个)。数组元素是计算4个方向下一点的偏移值，便于计算各方向的下一位置。
int direction[4][2]={-1,0,0,1,1,0,0,-1};
（4）算法的基本思想：
1）从入口出发，采用试探方法，搜索到目标点(出口)的路径，遇到出口则成功结束。
2）遇到分支点时选一个方向向前探索，这时需纪录当时的分支点和在这里已试探过的分支(和尚未试探过的分支)。
3）若遇到死路(所有方向都不能走或已试探过)，就退回前一分支点，换一方向再探索。直到找到目标，或者所有可能通路都探索到为止。这类方法称为回溯法。
4）每次回退(回溯)时总是去考虑最近纪录的那个分支点，如果最近分支点已经没有其它选择，就把它删除；
5）纪录和删除具有后进先出性质，可以用栈保存分支点信息；
6）遇到分支点将相关信息压入栈，删除分支点时将它弹出。
要求：入口、出口坐标为输入参数。如找到路径，则正向输出路径经过的每个矩阵元素的位置信息，矩阵元素之间用“->”分隔。每行超过4个矩阵元素则换行输出。如找不到路径，则输出"No Path"。为保证和测试数据一致，探索顺序应按照提示的顺序进行。
参考函数原型：
template<class ElemType>
void maze_path( SqStack<ElemType> &S, int row, int col, node enter, node outer, int **maze );
辅助函数：
（1）bool make2DArray(int row,int col, int ** &maze); //二位数组空间申请
（2）bool InputMaze(int row, int col, int ** &maze); //迷宫矩阵输入
（3）顺序栈ADT基本操作函数：若栈不空，则用e返回S的指定位置元素，并返回TRUE；否则返回FALSE。
template<class ElemType>
bool SqStack<ElemType>::GetElement(int pos, ElemType &e) const;
（4）模板参数ElemType设定为node（struct类型）
//迷宫专用结点类型
struct node{
int x,y;
int dir;
};
输入说明 :
第一行：迷宫矩阵的行数row 列数col
第二行：入口位置信息
第三行：出口位置信息
第四行-第（4+row）行：迷宫矩阵
输出说明 :
路径信息：每一行最多包含路径上4个点的位置信息，点与点之间用"->"分隔。如未找到路径，则输出"No Path"。
输入范例 :
10 10
0 0
9 9
0 0 1 1 1 1 1 0 0 0
1 0 1 0 0 0 0 0 1 1
1 0 0 0 1 1 0 1 1 1
1 1 0 1 1 1 0 1 1 0
1 1 0 1 1 1 0 0 0 1
1 0 0 1 1 1 0 1 1 1
1 1 0 0 0 0 0 1 1 1
1 1 0 1 1 0 1 1 1 1
1 1 1 1 1 0 0 0 0 0
1 1 1 1 1 0 1 1 0 0
输出范例
(0,0)->(0,1)->(1,1)->(2,1)->
(2,2)->(2,3)->(1,3)->(1,4)->
(1,5)->(1,6)->(2,6)->(3,6)->
(4,6)->(5,6)->(6,6)->(6,5)->
(7,5)->(8,5)->(8,6)->(8,7)->
(8,8)->(8,9)->(9,9)
AC可参考：
https://blog.csdn.net/VagetableOfPeng/article/details/102626731
