一、目的
1、进一步理解和掌握各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法。
2、掌握分析问题，求解问题的方法并提高设计编程实现的能力。
3、熟练掌握C语言或者C++语言的各种操作，制定清晰的程序流程图和数据结构的详细定义。
二、实验具体内容
1、用回溯法求解迷宫问题，可以用一个栈保存探索的位置。并且在该迷宫的行走中，站在一点可以有四个方向选择，依次判断四个方向是否能走。
2、定义一个固定格式（10*10）迷宫如下：
```
{ 0,1,1,1,0,0,0,0,0,0,
0,0,0,1,0,0,0,1,0,0,
0,1,0,1,1,0,0,1,0,0,
0,1,0,0,1,0,1,1,0,0,
0,1,0,0,1,0,1,1,0,0,
1,1,1,0,1,0,1,0,0,0,
0,0,1,0,0,0,1,0,1,1,
0,0,1,0,0,0,1,0,1,1,
0,1,1,0,1,0,1,0,0,0,
0,0,0,0,1,0,1,1,0,0, };
```
3、并设置左上角（0，0）为入口，右下角（9，9）为出口，0表示通路，1表示有墙。
4、用二维数组MAZE[x][y] 来表示迷宫的状态，0表示通路，1表示有墙，2表示已经走过。
5、用STL的栈储存走过的路径，压栈表示进入下一步，退栈表示返回上一步。每个栈元素是当前位置坐标被结构体对象包装产生的。
三、分析
首先要考虑如何判断行进方向，并且确定下一个方向可以走，再考虑如何判定走过的路，这里我采用的是将其值设置为2，然后每走一步就将这个位置包装起来压栈，假如无法再继续行走的话就进行回溯，相当于原路返回，伴随的还有之前压入的错误路径的栈元素要出栈，反复进行从而将所有正确位置压入栈中，由栈底往栈顶遍历，从而输出正确路径。
四、代码
结构体定义：
```
struct pos{
int i,j;
};
```
方向判定：
判断是否有通路，有则返回通路位置，无则返回原来位置
//向上
if(判定是否是通路且是否在迷宫范围之内且是否已经走过了){
执行位置变动和将此位置标记为已走，返回下个位置
}//向右
else if(判定是否是通路且是否在迷宫范围之内且是否已经走过了){
执行位置变动和将此位置标记为已走，返回下个位置
}//向下
else if(判定是否是通路且是否在迷宫范围之内且是否已经走过了){
执行位置变动和将此位置标记为已走，返回下个位置
}//向左
else if(判定是否是通路且是否在迷宫范围之内且是否已经走过了){
执行位置变动和将此位置标记为已走，返回下个位置
}
否则返回上一个位置。
数据结构操作：
stack Path;
声明两个结构体对象curr，nex；
将接收入栈元素的结构体对象curr初始化为入口元素，i=0，j=0；
将入口元素入栈；
将入口（0，0）设置成走过的位置；
```
while(判断栈是否为空){
curr=栈顶;
nex=curr;
nex=Move(curr);//将curr传入Move函数判断方向并行走，从而发现通路返回下个位置或者没有发现通路返回上个位置
if(!(curr.i==nex.i&&curr.j==nex.j))
发现通路，将nex压入栈顶；
else
未发现通路，将栈顶出栈；
if(判断nex是否到达出口（9，9）){
struct posroute[Path.size()];
intz=0;
while(判断栈时候为空，不空执行下列程序，空则跳出){
curr=栈顶元素；
将栈顶元素放入route结构体类型数组中；
栈顶出栈，以便下次操作；
}
for(intk=z-1;k>=0;k--){
按规格输出路径；
}
return;
}
}
cout<<"NO Path!"<
```
主函数：自行想象.......
五、运行结果
迷宫如下：
0 1 1 1 0 0 0 0 0 0
0 0 0 1 0 0 0 1 0 0
0 1 0 1 1 0 0 1 0 0
0 1 0 0 1 0 1 1 0 0
0 1 0 0 1 0 1 1 0 0
1 1 1 0 1 0 1 0 0 0
0 0 1 0 0 0 1 0 1 1
0 0 1 0 0 0 1 0 1 1
0 1 1 0 1 0 1 0 0 0
0 0 0 0 1 0 1 1 0 0
则路径为：
(0,0)->(1,0)->(1,1)->(1,2)->(2,2)
->(3,2)->(3,3)->(4,3)->(5,3)->(6,3)
->(6,4)->(6,5)->(5,5)->(4,5)->(3,5)
->(2,5)->(1,5)->(0,5)->(0,6)->(0,7)
->(0,8)->(0,9)->(1,9)->(2,9)->(3,9)
->(4,9)->(5,9)->(5,8)->(5,7)->(6,7)
->(7,7)->(8,7)->(8,8)->(8,9)->(9,9)
网友评论