迷宫问题.docx
《迷宫问题.docx》由会员分享，可在线阅读，更多相关《迷宫问题.docx（18页珍藏版）》请在冰点文库上搜索。
迷宫问题
第二次上机报告迷宫问题
一．上机目的：
通过使用系统栈（函数递归调用）与自定义栈寻找迷宫的一条路径来加深对于栈的特点的理解以及熟练对栈的使用，体会栈这一特殊数据结构的用处与优点。
了解如何使用栈来实现深度优先搜索。
利用队列寻找迷宫的一条最短路径，来加深对于队列的特点的理解以及熟练对队列的使用，体会队列这一特殊数据结构的用处与优点。
了解如何使用队列来实现广度优先搜索。
二．问题描述：
利用系统栈以及自定义栈求一条迷宫路径：
有一个m×n的迷宫，利用深度优先搜索，找到一条从起点（默认为（1,1））到终点（默认为（m-2,n-2））的路径。
用系统栈时输出到屏幕，用自定义栈时输出到文件。
利用队列求迷宫最短路径：
有一个m×n的迷宫，利用广度优先搜索，找到一条从起点（默认为（1,1））到终点（默认为（m-2,n-2））的最短路径，并输出到文件。
三．数据结构与算法：
数据结构：
1.自定义栈：
类的定义（类的实现参见程序）：
栈类（类模板）：
template
classstack{
public:
voidclear（）;//清空栈
boolpush（constTitem）;//入栈//传入const常数，以防修改
boolpop（）;//出栈
boolreadtop（T&item）;//读取栈顶元素,赋值给item
boolisempty（）;//判断是否为空栈
boolisfull（）;//判断是否为满栈
};
顺序栈类（类模板）:
template
classarrstack:
publicstack{
private:
intmsize;//栈的大小，最多能存放的元素个数
inttop;//栈顶指针
T*st;//存放栈中元素的数组
public:
arrstack（intsize）;//创建一个给定长度的顺序栈
arrstack（）;//创建一个顺序栈，无大小
~arrstack（）;//析构函数
voidclear（）;//清空栈
boolpush（constTitem）;//入栈
boolpop（）;//出栈
boolreadtop（T&item）;//读栈顶元素
boolisempty（）{return（top==-1）;}//判断是否栈空
boolisfull（）{return（top==msize-1）;}//判断是否栈满
};
2.自定义队列：
类的定义（类的实现参见程序）：
队列类（类模板）：
template
classqueue{
public:
voidclear（）;
boolenqueue（constTitem）;//入队
booldequeue（T&item）;//出队，将队首元素赋值给item
boolgetfront（T&item）;//读队首元素，赋值给item
boolisempty（）;//判断是否队空
boolisfull（）;//判断是否队满
};
顺序队列类（类模板）：
template
classarrqueue:
publicqueue{
private:
intmsize;//元素个数的最大值
intfront;//头指针（伪指针）
intrear;//尾指针（伪指针）
T*qu;//存放元素的数组
public:
arrqueue（intsize）；//构造函数
~arrqueue（）；//析构函数
voidclear（）；//清空队列
boolenqueue（constTitem）；//入队
booldequeue（T&item）；//出队
boolgetfront（T&item）；//读队首
boolisempty（）；//判断是否队空
boolisfull（）；//判断是否队满
};
迷宫点类A（利用自定义栈求一条迷宫路径中）：
classmazepoint{
private:
intx,y;//本身的坐标
intd;//已经走到的方向序数
boolwall;//是不是墙
boolvisited;//是否已经访问过
public:
mazepoint（）{
d=-1;
wall=false;
visited=false;
}
mazepoint（mazepoint&mp）{
x=mp.x;
y=mp.y;
d=mp.d;
wall=mp.wall;
visited=mp.visited;
}
voidcopy（mazepoint&mp）{
x=mp.x;
y=mp.y;
d=mp.d;
wall=mp.wall;
visited=mp.visited;
}
boolgetwall（）{returnwall;}
voidsetpos（intnx,intny）{x=nx;y=ny;}
voidsetwall（boolwal）{wall=wal;}
voidsetd（intnd）{d=nd;}
voidsetvisited（boolvis）{visited=vis;}
voidgetpos（int&xx,int&yy）{xx=x;yy=y;}
friendmazepoint**mazeinit（intm,intn）;
friendvoidmazepath（mazepoint**maze,intdirection[][2],intx1,inty1,intx2,inty2）;
friendvoidprintpath（arrstack&mps）;
};
迷宫点类B（利用队列求迷宫最短路径中）：
classmazepoint{
private:
intx,y;//本身的坐标
intpx,py;//前驱结点坐标
boolvisited;//是否被访问过
boolwall;//是不是墙
public:
mazepoint（）{
px=-1;
py=-1;
visited=0;
wall=false;
}
mazepoint（constboolwal）{
x=-1;
y=-1;
px=-1;
py=-1;
visited=0;
wall=wal;
}
mazepoint（mazepoint&mp）{
x=mp.x;
y=mp.y;
px=mp.px;
py=mp.py;
visited=mp.visited;
wall=mp.wall;
}
voidcopy（mazepoint&mp）{
x=mp.x;
y=mp.y;
px=mp.px;
py=mp.py;
visited=mp.visited;
wall=mp.wall;
}
boolgetwall（）{returnwall;}
boolgetvisited（）{returnvisited;}
voidgetprepos（int&xx,int&yy）{xx=px;yy=py;}
voidsetvisited（boolvis）{visited=vis;}
voidsetpos（intnx,intny）{x=nx;y=ny;}
voidsetprepoint（intppx,intppy）{px=ppx;py=ppy;}
voidsetwall（boolwal）{wall=wal;}
voidgetpos（int&xx,int&yy）{xx=x;yy=y;}
friendvoidprintpath（mazepoint**maze,intx1,inty1,intx2,inty2）;
friendvoidmazepath（mazepoint**maze,intdirection[][2],intx1,inty1,intx2,inty2）;
};
算法:
1.利用系统栈求一条迷宫路径：
使用到的函数如下：
boolmazepath（intmaze[][11],intdirection[][2],intx1,inty1,
intx2,inty2）；
a．迷宫初始化及相关量地定义：
由于系统栈不是这次上机的重点，其目的也只是体会函数递归调用的过程，所以我尽量将其编的简单，迷宫由一个二维int型数组来实现，在定义时就给定，比如我现在程序中使用的迷宫就是：
intmaze[][11]={1,1,1,1,1,1,1,1,1,1,1,
1,0,1,0,0,1,1,1,0,0,1,
1,0,0,0,0,0,1,0,0,1,1,
1,0,1,1,1,0,0,0,1,1,1,
1,0,0,0,1,0,1,1,0,1,1,
1,1,0,0,1,0,1,1,0,0,1,
1,1,1,0,0,0,0,0,0,0,1,
1,1,1,1,1,1,1,1,1,1,1};
另外，为了使得方向的表示尽量方便以及程序向n维迷宫的可拓展性，我借鉴了薛建明老师的方法，也就是采用数组：
intdirection[][2]={0,1,1,0,0,-1,-1,0};
来表示上下左右四个方向，使用时只需要采用以下语句：
x=x1+direction[i][0];
y=y1+direction[i][1];
b．函数递归调用:
我定义了函数mazepath来实现路径的求解。
首先mazepath的返回值是bool型，在mazepath中利用以下语句：
for（i=0;i<4;i++）{//四个方向循环
x3=x1+direction[i][0];//得到新坐标
y3=y1+direction[i][1];
……
}
依次向四个方向走得到新坐标，每得到一个新坐标，就判断是否到达递归调用的出口：
if（x3==x2&&y3==y2&&maze[x3][y3]==0）{//如果到出口
cout<<"（"<cout<<"<-（"<returntrue;//返回true
然后再判断能否以新坐标作为起点进入下一层函数：
elseif（maze[x3][y3]==0）{//不是出口但是可以走
maze[x3][y3]=2;//标记走过了
b=mazepath（maze,direction,x3,y3,x2,y2）;//进入下一层
……
}
当从下一层函数规定的起点已经走通时，用b接收下层函数的返回值为true，说明变更起点后已经走通，而变更的起点是在这一层函数走到的，所以从这一层函数的起点也可以找到一条路径到终点，打印这层函数规定的起点，然后再返回给上层函数true，如此实现从终点一直反馈到初始起点，即找到一条路径。
若没有打印出任何东西则说明一条路径也没找到。
具体实现的语句如下:
elseif（maze[x3][y3]==0）{//不是出口但是可以走
maze[x3][y3]=2;//标记走过了
b=mazepath（maze,direction,x3,y3,x2,y2）;
//设置新入口，递归调用，b接收下层函数的返回值
if（b==1）{//若返回值为true，表示这条路走得通.
cout<<"<-（"<returntrue;//继续向上返回true
}
}
以上就是利用系统栈求一条迷宫路径的具体算法分析，虽然很简单，但是递归调用的思想是很重要的，即要有一个递归出口以及进入下一层递归的条件。
我这个程序的特点是加上了对于程序返回值的处理，使得程序的效率比较高。
2．利用自定义栈求一条迷宫路径：
使用到的函数如下：
//初始化迷宫
mazepoint**mazeinit（intm,intn）；
//求迷宫路径
voidmazepath（mazepoint**maze,intdirection[][2],intx1,inty1,intx2,inty2）；
//打印迷宫路径
voidprintpath（arrstack&mps）；
a.迷宫初始化以及相关量的定义
为了体现C++的特性，我采用了自定义类的形式来表示迷宫，具体地说就是定义了一个迷宫点类mazepoint，其数据成员包括该点的坐标（x,y）、从该点已经走了的方向序数（d）、该点是否被访问过的标记（visited）、该点是否是墙的标记（wall）。
方向的表示同系统栈。
我用一个mazepoint的二级指针mazepoint**maze来表示迷宫，支持自定义迷宫的大小，即可以输入两个正整数m，n，来生成一个m×n的迷宫。
迷宫初始化过程在mazepoint**mazeinit（intm,intn）中实现：
这里要用到二级指针的内存分配，具体实现如下：
mazepoint**maze=newmazepoint*[m];
for（i=0;imaze[i]=newmazepoint[n];
接下来将各个点定位：
for（i=0;ifor（j=0;jmaze[i][j].setpos（i,j）;
}
}
时间代价为O（m*n）。
接下来初始化墙：
先将边界全部设为墙，再按行来操作，1,3,5，……奇数行没有墙，偶数行随机生成墙（保证终点不为墙），目的是为了防止因随机设墙而造成经常找不到一条通路，具体实现见代码。
初始化完成后，将迷宫输出到“maze.txt”文件，并返回到main（）中。
b.求解迷宫的一条路径：
进入函数voidmazepath（mazepoint**maze,intdirection[][2],intx1,inty1,intx2,inty2）:
定义一个栈来保存路径上的点：
arrstackmazestack（200）;
入口标记后入栈。
进入循环（条件是栈不为空，若为空，则说明一条路径也找不到）：
读栈顶到mp，临时方向b由mp确定，目的是紧接着上次未走的方向开始走。
然后判断是否弹出的就是出口，若是，则输出路径并退出函数（return）。
若不是出口，则弹出栈顶元素，从mp表示的点依次沿四个方向走，若新坐标位置不是墙且未被访问过，则将mp的方向序数d用临时方向d赋值，原位置入栈，新位置标记成已访问过，新位置入栈，跳出方向循环，进入下一次出栈的操作，如此往复进行，直到弹出的是出口。
关键步骤具体实现如下：
for（d++;d<4;d++）{//d++防止重复走一个方向（每个新点的d初值都为-1）//四个方向循环
nx=mp.x+direction[d][0];//计算新位置
ny=mp.y+direction[d][1];
if（（!
maze[nx][ny].wall）&&（!
maze[nx][ny].visited））{//不为墙且未访问过
mp.setd（d）;//记录方向
mazestack.push（mp）;//前一点入栈
maze[nx][ny].setvisited（true）;//标记已经访问过了，避免走回头路
mazestack.push（maze[nx][ny]）;//后一点入栈
break;
}
}
c.路径的打印：
进入函数voidprintpath（arrstack&mps）；
打开文件输出fout到“mazepath.txt”，当mps不空时，读入栈顶到mp，出栈，打印mp的坐标即可，注意一下输出的格式：
fout<<"（";
fout<（2）<fout<（2）<if（i%10==0）fout<i++;
其中i用来控制换行
当路径打印完毕后，关闭输出。
以上就是用自定义栈求迷宫一条路径的算法，重点是入栈的操作，入哪几个的元素以及对于元素的相关处理（visited与d）。
3.利用队列求迷宫最短路径：
使用到的函数如下：
//初始化迷宫
mazepoint**mazeinit（intm,intn）；
//求迷宫路径
voidmazepath（mazepoint**maze,intdirection[][2],intx1,inty1,intx2,inty2）；
//打印路径
voidprintpath（mazepoint**maze,intx1,inty1,intx2,inty2）；
a.迷宫初始化及相关量的定义
初始化工作（direction，maze）与用自定义栈找路径中的初始化类似。
唯一的差别在于mazepoint数据成员为该点坐标（x，y）、该点前驱的坐标（px，py）、标记（wall、visited），原因是最后打印路径时要从终点开始，找前驱结点，一直找到起点。
b.求解迷宫的一条最短路径：
此程序的重点是利用队列的特点实现广度优先搜索。
进入函数voidmazepath（mazepoint**maze,intdirection[][2],intx1,inty1,intx2,inty2）；
建立队列mpqueue,临时迷宫点mp。
起点入队。
进入循环（当mpqueue不为空时）：
读队头给mp，得到mp的坐标（xx，yy），判断mp是否为出口，若是，则打印路径。
若不是，则四个方向依次走一步，若新坐标位置不为墙且未被访问过，则标记成访问过，并设置新位置的前驱为原结点，新位置入队。
再进行下一轮操作，若队列为空，则一条路径也没找到。
重要步骤的实现如下：
while（!
mpqueue.isempty（））{//队列不空且不为出口{
mpqueue.dequeue（mp）;//读取队列头赋值给mp并使出队
mp.getpos（xx,yy）;//得到当前结点的位置,赋值给xx与yy
if（xx==x2&&yy==y2）{//找到出口
printpath（maze,x1,y1,x2,y2）;//打印路径
return;
}
for（k=0;k<4;k++）{//上下左右四个位置检查并处理
tmpx=xx+direction[k][0];
tmpy=yy+direction[k][1];
if（maze[tmpx][tmpy].wall==0&&maze[tmpx][tmpy].visited==0）{//如果该处不是墙且没有被走过
maze[tmpx][tmpy].setvisited（true）;//标记走过了
maze[tmpx][tmpy].setprepoint（xx,yy）;//标记前一点，为了以后打印路径
mpqueue.enqueue（maze[tmpx][tmpy]）;//入队
}
}
}
c.打印路径：
从终点开始，赋值给临时迷宫点mp，先打印当前mp的位置到文件“mazepath.txt”，再用mp的前驱覆盖mp，进入下一轮操作，直到找到起点。
打印格式同系统栈。
四．结果分析：
1.利用系统栈求一条迷宫路径：
迷宫初始化为intmaze[][11]={1,1,1,1,1,1,1,1,1,1,1,
1,0,1,0,0,1,1,1,0,0,1,
1,0,0,0,0,0,1,0,0,1,1,
1,0,1,1,1,0,0,0,1,1,1,
1,0,0,0,1,0,1,1,0,1,1,
1,1,0,0,1,0,1,1,0,0,1,
1,1,1,0,0,0,0,0,0,0,1,
1,1,1,1,1,1,1,1,1,1,1};
路径为：
（6,9）<-（6,8）<-（6,7）<-（6,6）<-（6,5）<-（5,5）<-（4,5）<-（3,5）<-（2,5）,（2,4）<-（2,3）<-（2,2）<-（2,1）<-（1,1）
2.利用自定义栈求一条迷宫路径：
输入m=40，n=40的一种可能情况是：
“maze.txt”中：
“mazepath.txt”中：
（38,38）<-（37,38）<-（37,37）<-（37,36）<-（37,35）<-（36,35）<-（35,35）<-（35,36）<-（35,37）<-（35,38）<-
（34,38）<-（33,38）<-（32,38）<-（31,38）<-（31,37）<-（31,36）<-（31,35）<-（31,34）<-（30,34）<-（29,34）<-
（29,35）<-（29,36）<-（29,37）<-（28,37）<-（27,37）<-（26,37）<-（25,37）<-（25,38）<-（24,38）<-（23,38）<-
（22,38）<-（21,38）<-（21,37）<-（20,37）<-（19,37）<-（19,36）<-（19,35）<-（18,35）<-（17,35）<-（17,36）<-
（17,37）<-（17,38）<-（16,38）<-（15,38）<-（15,37）<-（14,37）<-（13,37）<-（13,38）<-（12,38）<-（11,38）<-
（10,38）<-（9,38）<-（9,37）<-（8,37）<-（7,37）<-（7,38）<-（6,38）<-（5,38）<-（4,38）<-（3,38）<-
（2,38）<-（1,38）<-（1,37）<-（1,36）<-（1,35）<-（1,34）<-（1,33）<-（1,32）<-（1,31）<-（1,30）<-
（1,29）<-（1,28）<-（1,27）<-（1,26）<-（1,25）<-（1,24）<-（1,
升级会员 