c++课程设计迷宫问题求解.docx
《c++课程设计迷宫问题求解.docx》由会员分享，可在线阅读，更多相关《c++课程设计迷宫问题求解.docx（16页珍藏版）》请在冰点文库上搜索。
c++课程设计迷宫问题求解
设计题目
迷宫问题求解
任务
迷宫问题是取自心理学的一个古典实验。
实验中，把一只老鼠从一个没有顶的大盒子的门放入，在盒中设置了许多墙，对行进的方向形成了多处阻挡。
盒子仅仅有一个出口，在出口处放置了一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。
重复对老鼠进行上述实验，看老鼠能在多久找到出口。
功能要求：
请设计一个算法实现迷宫问题求解。
测试数据：
0表示可以行走的区域，1表示不可行走的区域。
入口
1
0
0
0
1
0
1
1
0
1
0
1
1
0
1
1
0
1
1
0
0
1
0
1
1
1
1
0
出口
需求分析
该程序的实现需要用到栈，用栈来储存正确的步骤。
首先要建立一个迷宫，用数组来实现。
然后通过规定的放向依次探索，一步步找到正确的路径。
概要设计
typedefstructStackElem
{
intx;
inty;
intf;}StackElem;
//定义栈
typedefstruct
{
StackElem*base;
StackElem*top;
intStackSize;
}Stack;
//初始化栈
voidStackInit（Stack*s）
//向栈中添加元素
voidPush（Stack*s,StackEleme）
//获得栈顶元素
StackElemGetTop（Stack*s）
/删除栈顶元素
voidPop（Stack*s）
/判断当前位置是否走过（下一位置与Path中所有位置从栈顶至栈底依次比较）
intunPass（StackPath,StackElemStep
/右边相邻的位置
StackElemRight（StackElemStep,intm,intn）（一共8个向函数类似）
//获得下一个可通行的位置,逐个方向试探
StackElemGetNext（StackElemStep,intm,intn）
intGetMazePath（intm,intn）{//获得迷宫路径
/打印迷宫路径
voidPrintMazePath（Stack*s）
voidmain（）{
inti,j;
printf（"********迷宫********\n"）;
printf（"0是通路\n1是墙\n"）;
printf（"请输入行数（<=100）:
"）;
scanf（"%d",&m）;
printf（"请输入列数（<=100）:
"）;
scanf（"%d",&n）;
printf（"请输入迷宫数据（按行来）:
\n"）;
for（i=0;ifor（j=0;jscanf（"%d",&maze[i][j]）;
printf（"迷宫:
\n"）;
for（i=0;i{
for（j=0;jprintf（"\t%d",maze[i][j]）;
printf（"\n"）;
}
StackInit（&RealPath）;
StackInit（&Path）;
GetMazePath（m,n）;
printf（"路径是:
\n"）;
PrintMazePath（&RealPath）;
printf（"\n"）;
}
程序调用关系如下：
主程序模块
获得迷宫初始化栈找到路径
详细设计
//
#include"stdafx.h"
#include"stdlib.h"
#include"conio.h"
#defineTRUE1
#defineFAUSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
#defineOVERFLOW-2
#defineNULL0
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
//定义栈元素
typedefstructStackElem
{
intx;//x坐标
inty;//y坐标
intf;//maze[x][y]的值
}StackElem;
//定义栈
typedefstruct
{
StackElem*base;
StackElem*top;
intStackSize;
}Stack;
//初始化迷宫,0表示通道,1表示墙
intmaze[100][100]={0};
intm,n;
//栈操作的实现
//初始化栈
voidStackInit（Stack*s）
{
s->base=（StackElem*）malloc（STACK_INIT_SIZE*sizeof（StackElem））;
if（!
s->base）{
printf（"内存分配失败!
\n"）;
exit（OVERFLOW）;//内存分配失败
}
s->top=s->base;
s->StackSize=STACK_INIT_SIZE;
}
//向栈中添加元素
voidPush（Stack*s,StackEleme）
{
if（s->top-s->base>=s->StackSize）{//栈满,增加空间
s->base=（StackElem*）realloc（s->base,（STACK_INIT_SIZE+STACKINCREMENT）*sizeof（StackElem））;
if（!
s->base）{
printf（"内存分配失败.\n"）;
exit（OVERFLOW）;//内存分配失败
}
s->top=s->base+s->StackSize;//分配空间后重置栈顶指针
s->StackSize+=STACKINCREMENT;}//空间再分配完成
*（s->top++）=e;//将新元素加到栈顶
}
//获得栈顶元素
StackElemGetTop（Stack*s）
{
if（s->top==s->base）{
printf（"没有路径可以走出迷宫!
\n"）;
exit（ERROR）;}
else{return*（s->top-1）;}
}
//删除栈顶元素
voidPop（Stack*s）
{//若栈不为空,则删除s的栈顶元素
if（s->top==s->base）{
printf（"没有路径可以走出迷宫!
\n"）;
exit（ERROR）;
}
else{--（s->top）;}
}
//迷宫求解
//构造两个栈,Path用来保存探索中的全部路径,RealPath用来保存有效路径
StackRealPath,Path;
//判断当前位置是否走过（下一位置与Path中所有位置从栈顶至栈底依次比较）
intunPass（StackPath,StackElemStep）{
intMark=1;
while（Path.top!
=Path.base）//非空
{
StackEleme=*（Path.top-1）;//栈顶
if（e.x==Step.x&&e.y==Step.y）
{Mark=0;}
（Path.top）--;
}
returnMark;
}
//右边相邻的位置
StackElemRight（StackElemStep,intm,intn）{
if（Step.y!
=n-1）{
Step.y++;
Step.f=maze[Step.x][Step.y];
}
returnStep;//当y==n-1时返回它本身
}
//下面相邻的位置
StackElemDown（StackElemStep,intm,intn）{
if（Step.xStep.x++;
Step.f=maze[Step.x][Step.y];
}
returnStep;//当x==m-1时返回它本身
}
//左边相邻的位置
StackElemLeft（StackElemStep,intm,intn）{
if（Step.y!
=0）{
Step.y--;
Step.f=maze[Step.x][Step.y];
}
returnStep;//当y==0时返回它本身
}
//上面相邻的位置
StackElemUp（StackElemStep,intm,intn）{
if（Step.x!
=0）{
Step.x--;
Step.f=maze[Step.x][Step.y];
}
returnStep;//当Step.x==0时返回它本身
}
//左上相邻的位置
StackElemLU（StackElemStep,intm,intn）{
if（Step.x!
=0&&Step.y!
=0）{
Step.x--;
Step.y--;
Step.f=maze[Step.x][Step.y];
}
returnStep;//当x==0&&y==0时返回它本身
}
//右上相邻的位置
StackElemRU（StackElemStep,intm,intn）{
if（Step.x!
=0&&Step.yStep.x--;
Step.y++;
Step.f=maze[Step.x][Step.y];
}
returnStep;//当x==0&&y==n-1时返回它本身
}
//左下相邻的位置
StackElemLD（StackElemStep,intm,intn）{
if（Step.x=0）{
Step.x++;
Step.y--;
Step.f=maze[Step.x][Step.y];
}
returnStep;//当Step.x==m-1&&y==0时返回它本身
}
//右下相邻的位置
StackElemRD（StackElemStep,intm,intn）{
if（Step.xStep.x++;
Step.y++;
Step.f=maze[Step.x][Step.y];
}
returnStep;//当Step.x==0时返回它本身
}
//获得下一个可通行的位置,逐个方向试探
StackElemGetNext（StackElemStep,intm,intn）{
StackElemnext;
next.f=-1;
if（Right（Step,m,n）.f==0&&unPass（Path,Right（Step,m,n）））//右通路（右元素为且未走过）
{next=Right（Step,m,n）;}
elseif（Down（Step,m,n）.f==0&&unPass（Path,Down（Step,m,n）））//下通路
{next=Down（Step,m,n）;}
elseif（Left（Step,m,n）.f==0&&unPass（Path,Left（Step,m,n）））//左通路
{next=Left（Step,m,n）;}
elseif（Up（Step,m,n）.f==0&&unPass（Path,Up（Step,m,n）））//上通路
{next=Up（Step,m,n）;}
elseif（RD（Step,m,n）.f==0&&unPass（Path,RD（Step,m,n）））//右下通路
{next=RD（Step,m,n）;}
elseif（LD（Step,m,n）.f==0&&unPass（Path,LD（Step,m,n）））//左下通路
{next=LD（Step,m,n）;}
elseif（RU（Step,m,n）.f==0&&unPass（Path,RU（Step,m,n）））//右上通路
{next=RU（Step,m,n）;}
elseif（LU（Step,m,n）.f==0&&unPass（Path,LU（Step,m,n）））//左上通路
{next=LU（Step,m,n）;}
//如果当前位置的四面或为墙或已走过,则返回的next的f值为-1
returnnext;
}
intGetMazePath（intm,intn）{//获得迷宫路径
StackElemstart,end,Step;
start.x=0;
start.y=0;
start.f=maze[start.x][start.y];
end.x=m-1;
end.y=n-1;
end.f=maze[end.x][end.y];
Step=start;//设定当前为位置为"入口位置"，对新迷宫进行求解
while（Step.x!
=end.x||Step.y!
=end.y）
{
if（unPass（Path,Step））//如果当前位置未走到过
{
Push（&RealPath,Step）;
Push（&Path,Step）;
Step=GetNext（Step,m,n）;
if（Step.x==end.x&&Step.y==end.y）//到达出口,结束递归
{
Push（&RealPath,Step）;//出口位置
Push（&Path,Step）;
returntrue;
}
elseif（Step.f==-1）
{
Pop（&RealPath）;
Step=GetTop（&RealPath）;//令Step指向栈顶元素
}
}
else{//如果当前位置已经走过,说明原来测试的方向不对,现在尝试其它方向
Step=GetNext（Step,m,n）;
if（Step.f==-1）{//仍不通,删除真实路径的栈顶元素，返回上一步
Pop（&RealPath）;
Step=GetTop（&RealPath）;
}
}
};
}
//打印迷宫路径
voidPrintMazePath（Stack*s）{
StackEleme;
while（s->base<（s->top-1））
{
e=*（s->base）;//先指向栈底元素,以后依次向上增
printf（"[%d][%d]-->",e.x,e.y）;
（s->base）++;
}
e=*（s->base）;
printf（"[%d][%d]",e.x,e.y）;
}
voidmain（）{
inti,j;
printf（"********迷宫********\n"）;
printf（"0是通路\n1是墙\n"）;
printf（"请输入行数（<=100）:
"）;
scanf（"%d",&m）;
printf（"请输入列数（<=100）:
"）;
scanf（"%d",&n）;
printf（"请输入迷宫数据（按行来）:
\n"）;
for（i=0;ifor（j=0;jscanf（"%d",&maze[i][j]）;
printf（"迷宫:
\n"）;
for（i=0;i{
for（j=0;jprintf（"\t%d",maze[i][j]）;
printf（"\n"）;
}
StackInit（&RealPath）;
StackInit（&Path）;
GetMazePath（m,n）;
printf（"路径是:
\n"）;
PrintMazePath（&RealPath）;
printf（"\n"）;
}
调试分析
a.在走到死路要回去时，开始的设计中使得程序陷入了死循环一直向右走，在设计时要匹配好if与else的关系。
b.在设计输入时要把数量与数组下标结合起来，使其一致。
c.由于程序较大，栈的大小用数据直接来表示的话会出现混乱（自己搞混），通过学习书上的放在开头用单词来替代。
用户手册
（1）演示程序的运行环境为Windows10系统，MicrosoftVisualC++6.0中运行。
执行文件为：
迷宫求解.exe
（2）进入演示程序后即显示DOS形式的界面：
（3）、根据选择比赛是取前几名可以进入相应的界面
（4）、进入相应界面接受其他命令后即执行相应功能。
测试结果，输入行数和列数。
输入表格中的测试数据
查找结果：
升级会员 