迷宫源代码文档格式.docx
《迷宫源代码文档格式.docx》由会员分享，可在线阅读，更多相关《迷宫源代码文档格式.docx（16页珍藏版）》请在冰点文库上搜索。
&
ly==pos.ly）;
};
MazePosoperator=（constMazePospos）
wx=pos.wx;
ly=pos.ly;
pass=pos.pass;
path=pos.path;
return*this;
};
//End:
MazePos---------------------------------------
SElemType-----------------------------------------
//辅助栈元素类型
classSElemType
intord;
//迷宫通道块路径上的序号
MazePosseat;
//通道块在迷宫中的位置坐标
intdi;
//从此通道块走向下一通道块的方向
//0:
无效,1:
东,2:
南,3:
西,4:
北
booloperator==（constSElemTypeet）
return（seat==et.seat）;
SElemTypeoperator=（constSElemTypeet）
ord=et.ord;
seat=et.seat;
di=et.di;
return（*this）;
SElemType--------------------------------------
//struct:
MazeMap-------------------------------------
//由通道块组成的迷宫地图
#defineMAPWIDTH10
#defineMAPHEIGHT10
typedefstructMazeMap
//由通道块矩阵构成
MazePosmazemap[MAPWIDTH][MAPHEIGHT];
}MazeMap;
MazeMap---------------------------------------
:
MazeWay----------------------------------------
//辅助出口路径链表元素类型
typedefstructMazeWay
}MazeWay;
MazeWay--------------------------------------------
//Class:
Maze----------------------------------------
//主体类,迷宫路径问题求解
classMaze
Maze（intwidth=MAPWIDTH,intheight=MAPHEIGHT）;
//生成迷宫地图
~Maze（）;
voidDoMaze（）;
//找出出口路径并显示
private:
boolInitOK;
//初始化成功标志
MazeMapmap;
//迷宫地图
MazePosstart,end;
//迷宫的入口和出口
boolFindPath（）;
//主要函数,寻找出口路径
list<
MazeWay>
mazeway;
//存放出口路径的临时链表
voidRandMap（）;
//随机生成迷宫地图函数
boolCreateMap（boolinit）;
//在初始和找到出口路径后生成相应地图函数
boolpass（MazePoscurpos）;
//当前路径通道块是否可通（即是不是未经过的空块）
MazePosNextPos（MazePoscurpos,intdi）;
//取得当前通道块当前方向上的下一个通道块
boolInvalide（SElemTypee）;
//使当前通道块标记为不可通
voidDisplayMaze（）;
//显示迷宫地图
Maze:
Maze（intwidth,intheight）
//
//随机生成迷宫地图
CreateMap（true）;
//显示地图
DisplayMaze（）;
}
~Maze（）
//Addcodeshere
boolMaze:
FindPath（）
//寻找出口,并生成出口路径链表
if（InitOK）
//MazeStackmstack;
stack<
SElemType,list<
SElemType>
>
mstack;
MazePoscurpos=start;
intcurstep=1;
//经过的步数
MazeWaymw;
//出口路径块元素
unsignedmwsize=mazeway.size（）;
//为显示运行过程而设
do
if（pass（curpos））
//如果当前位置可通（即是未走过的空块）
//封装栈元素,将当前位置进栈
SElemTypee;
e.ord=curstep;
e.seat=curpos;
e.di=1;
mstack.push（e）;
//保存当前位置到出口路径链表
mw.wx=e.seat.wx;
mw.ly=e.seat.ly;
mazeway.push_back（mw）;
//如果是出口,则结束
if（curpos==end）
returntrue;
//不然就将得到下一个通道块
curpos=NextPos（curpos,e.di）;
curstep++;
}
else
//当前位置不可通,则在栈内找到下一个位置
if（!
mstack.empty（））
e=mstack.top（）;
mstack.pop（）;
//调整出口路径链表
mazeway.pop_back（）;
while（（e.di==0||e.di==4）&
!
mstack.empty（））
Invalide（e）;
//标记刻通道块不能通过
//退回一步
if（mstack.empty（））
returnfalse;
elseif（e.di<
5）
e.di++;
e.di=e.di%5;
curpos=NextPos（e.seat,e.di）;
///*//显示运行过程
if（mwsize!
=mazeway.size（））
CreateMap（false）;
mwsize=mazeway.size（）;
Sleep（800）;
//要包含windows.h头文件
//*
}while（!
mstack.empty（））;
MazePosMaze:
NextPos（MazePoscurpos,intdi）
MazePospos;
switch（di）
case1:
pos=map.mazemap[curpos.wx+1][curpos.ly];
break;
case2:
pos=map.mazemap[curpos.wx][curpos.ly+1];
case3:
pos=map.mazemap[curpos.wx-1][curpos.ly];
case4:
pos=map.mazemap[curpos.wx][curpos.ly-1];
returnpos;
pass（MazePoscurpos）
//通过MazePos类型参数传递的信息检查MazeMapmap;
if（curpos.wx<
0||
curpos.wx>
=MAPWIDTH||
curpos.ly<
curpos.ly>
=MAPHEIGHT）
return（map.mazemap[curpos.wx][curpos.ly].path==0&
map.mazemap[curpos.wx][curpos.ly].pass==false）;
voidMaze:
DoMaze（）
InitOK）
return;
if（FindPath（））
cout<
<
endl<
"
NOPATH!
endl;
RandMap（）
//只能生成从左上到右下的迷宫地图
MazeWaycurway;
//随机生成的当前正处理的出口路径块（组成mw）
mw;
//随机生成的出口路径（由curway组成）
iteratoriter;
//容器适配器
curway.wx=0;
curway.ly=1;
mw.push_back（curway）;
curway.wx++;
srand（time（0））;
//取得当前时间作为随机数种子
while（curway.wx<
MAPWIDTH-1&
curway.ly<
MAPHEIGHT-1）
if（rand（）%2==1）
//生成随机X坐标上的路径块
//生成随机Y坐标上的路径块
curway.ly++;
for（inty=0;
y<
MAPHEIGHT;
y++）
for（intx=0;
x<
MAPWIDTH;
x++）
//填充每个通道块
map.mazemap[x][y].wx=x;
map.mazemap[x][y].ly=y;
map.mazemap[x][y].pass=false;
if（x==0||y==0||x==MAPWIDTH-1||y==MAPHEIGHT-1）
//生成四周墙壁
map.mazemap[x][y].path=-1;
//map.mazemap[x][y].pass=true;
if（rand（）%10>
=6）//数值越小,墙壁越多
//随机生成墙壁
map.mazemap[x][y].path=0;
//生成空的通道块
//map.mazemap[x][y].pass=false;
}
//生成出口路径
for（iter=mw.begin（）;
iter!
=mw.end（）;
iter++）
map.mazemap[（*iter）.wx][（*iter）.ly].path=0;
//map.mazemap[（*iter）.wx][（*iter）.ly].pass=false;
//生成入口和出口
start=map.mazemap[mw.front（）.wx][mw.front（）.ly];
end=map.mazemap[mw.back（）.wx][mw.back（）.ly];
//初始化成功
InitOK=true;
CreateMap（boolinit）
if（init）
RandMap（）;
if（map.mazemap[x][y].path==0）
map.mazemap[x][y].pass=0;
for（iter=mazeway.begin（）;
=mazeway.end（）;
map.mazemap[（*iter）.wx][（*iter）.ly].path=1;
Invalide（SElemTypee）
//通过SElemType类型参数传递的信息修正MazeMapmap;
if（e.seat.wx<
0||
e.seat.wx>
=MAPWIDTH||
e.seat.ly<
e.seat.ly>
map.mazemap[e.seat.wx][e.seat.ly].pass=true;
DisplayMaze（）
switch（map.mazemap[x][y].path）
case-1:
█"
;
break;
//墙壁图案
case0:
"
//空块图案
=="
//出口路径图案
//main--------------------------------------------
//主函数,迷宫求解演示
intmain（intargc,char*argv[]）
下面是随机生成的迷宫:
Mazemymaze;
//生成迷宫
按任意键演示迷宫解法!
system（"
pause"
）;
mymaze.DoMaze（）;
演示结束."
return0;
升级会员 