迷宫求解
1． 实验要求
1. 实验目的
通过选择下面五个题目之一进行实现，掌握如下内容： ? 进一步掌握指针、模板类、异常处理的使用 ? 掌握栈的操作的实现方法 ? 掌握队列的操作的实现方法 ? 学习使用栈解决实际问题的能力 ? 学习使用队列解决实际问题的能力
2 .实验内容
利用栈结构实现迷宫求解问题。迷宫求解问题如下：
心理学家把一只老鼠从一个无顶盖的大盒子的入口赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口，测试算法的迷宫如下图所示。
提示：
1、可以使用递归或非递归两种方法实现
2、老鼠能够记住已经走过的路，不会反复走重复的路径 3、可以自己任意设置迷宫的大小和障碍 4、使用“穷举求解”的方法
2. 程序分析
2.1 存储结构
存储结构：顺序栈
data data data
top A3
top A2 A2
A1 A1 top
（1）空栈 (2)A1A2A3入栈 (3)A3出栈
2.2 关键算法分析
1.试探方向： （1）基本思想
每个点有4个方向去试探，如当前点的坐标(x , y)，与其相邻的4个点的坐标都可根据与该点的相邻方位而得到，如图所示。因为出口在（m，n），因此试探顺序规定为：从当前位置向前试探的方向为从正东沿顺时针方向进行。为了简化问题，方便的求出新点的坐标，将从正东开始沿顺时针进行的这4个方向（用0，1，2，3表示东、南、西、北）的坐标增量放在一个结构数组move [ 4 ]中，在move 数组中，每个元素有两个域组成，x：横坐标增量，y：纵坐标增量。
(x-1，y)
x y
0 0 1
1 1 0 (x，y-1) (x，y+1) (x，y)
2 0 -1
3 -1 0
(x+1，y) 与点 (x ， 相邻的 增量move数组 y)4 个点及坐标
（2）基本代码 struct item {
int x ; //行 int y ; //列
} ;
item move[4] ;
2.寻找路径
（1） 基本思想：
利用栈的结构，走过的路入栈，如果不能走出栈，采用遍历法，同时在二维数组中标记出已经走过的路径，因此栈内存储的数据就是寻一条路径，同时在二维数组中也有所体现。
当到达了某点而无路可走时需返回前一点，再从前一点开始向下一个方向继续试探。因此，压入栈中的不仅是顺序到达的各点的坐标，而且还要有从前一点到达本点的方向，即每走一步栈中记下的内容为(行，列，来的方向)。 （2） 代码 栈构造函数：
void seqstack::Push(int x,int y,int d) //入栈 { if(top>=StackSize-1)throw\上溢\ top++; data[top].d=d; data[top].x=x; data[top].y=y; }
寻找路径：
int seqstack::findpath(int a,int b,int m,int n) //寻找路径 { struct item { int x; //行 int y;//列 }; item move[4]={{0,1},{1,0},{0,-1},{-1,0}};//定义移动结构 int i, j ; Push(a,b,-1); //起点坐标入栈 int d=0,x=a,y=b; while(1) { if(Map[x][y]==0||Map[x][y]==2) pop(); x=data[top+1].x; y=data[top+1].y; data[top+1].d=data[top+1].d+1; d=data[top+1].d; if(d>3) { Map[x][y]=2; //用来标记已走过但并未走通的点
栈 }
}
if(top==-1) return 0;
} //d>3即代表从该点继续走无出路，所以退while (d<4) //方向是否可以移动 { i=x+move[d].x ; j=y+move[d].y ; //移动后坐标 if(Map[i][j]==0) //是否能移动 { Push(x,y,d); Map[x][y]=-1; //移动前坐标入栈 x=i; y=j; if(x==m&&y==n) //判断是否为终点坐标 { Push(x,y,-1); Map[x][y]=-1; return 1; } else d=0; } else d++ ; }
3.伪代码
a) 栈初始化;
b) 将入口点坐标及到达该点的方向（设为-1）入栈 c) while (1)
{
判断迷宫中试探方向的点是否可走或标出（可走则证明该点之前一个点已入栈）
出栈 ;
给x,y,data[top+1].d,d重新赋值
如果无试探方向，则用2标出该点之后就不用再走。 while （还有剩余试探方向时） { if （d方向可走）
则 { （x , y , d）入栈 ; 求新点坐标 (i, j ) ;
将新点（i , j）切换为当前点（x , y） ; if ( (x ,ｙ)= =(ｍ,n) ) 结束 ; else 重置 d=0 ;
