_迷宫问题
- 格式：doc
- 大小：120.50 KB
- 文档页数：6
迷宫问题实习报告
题目：编制一个求解迷宫通路的程序
班级：数字媒体技术一班姓名学号：1225149 完成日期：2013.10.29
一、需求分析
1 以二维数组BOX表示迷宫，在其周围加一圈围墙；数组中'1'表示障碍，'0'表示通路。
2 输入：用户手动键盘输入迷宫大小，再输入所要求的出口位置，再输入其中的障碍；
3.输出：若有通路，则输出路径（以坐标表示）；若无通路，则输出“该迷宫无通路”；
4.本程序只求出一条成功的通路。
然而，只需对迷宫求解的函数做小量修改即可求解全部路径。
5.测试数据：包括有通路的迷宫和无通路的迷宫。
二、概要设计
⒈为实现上述算法，需要线性表的抽象数据类型：
ADT Stack { 数据对象：D={ai:|ai∈ElemSet,i=1…n,n≥0} 数据关系：R1={<ai-1,ai>|ai-1,ai ∈D,i=2,…n≥0}
基本操作: initstack(& S)
操作结果：构造一个空的栈S。
StackLength(S)
初始条件：栈S已经存在
结果：返回S中数据元素的个数。
Stackempty(S)
初始条件：栈S已经存在
操作结果：判断S中是否为空，若为空，则返回TURE，否FALSE。
GetTop(S,&e)
初始条件：栈S已存在且不为空
操作结果：用e返回S的栈顶的元素。
Push(&S ,e)
初始条件：栈S已存在
操作结果：插入元素e为新的栈顶元素。
Pop(&S，&e)
初始条件：栈S已存在且不为空
操作结果：删除S的栈顶元素，并用e返回其值。
}ADT List
2. 本程序有三个模块：
⑴主程序模块
main(){
初始化；
寻找路径；
输出结果；
｝
｝
⑵栈单元模块：实现栈抽象数据类型；
⑶迷宫数组单元模块：设计迷宫，实现迷宫抽象数据类型。
(4) 路径查找模块：实现路径的查找。
各模块之间的调用关系是：主程序模块——路径查找模块——迷宫模块——栈模块。
三、详细设计
1.迷宫类型：
typedef struct
{
int i;
int j;
int di; //di为下一步方位号
}Box;
2.栈类型：
typedef struct
{
Box data[1000];
int top; //栈顶指针
}StType;
3.迷宫路径查找：
bool mgpath(int xi,int yi,int xe,int ye)
{
int i,j,k,di,find;
StType st;
st.top=-1;
st.top++;
st.data[st.top].i=xi; //进栈
st.data[st.top].j=yi;
st.data[st.top].di=-1;
mg[xi][yi]=-1;
while(st.top>-1) //当栈不为空时继续
{
i=st.data[st.top].i; //栈顶元素入栈
j=st.data[st.top].j;
di=st.data[st.top].di; //取出已搜索方向的方位号
if(i==xe&&j==xe) //如果已搜到目的地，则打印路径，并返回
{
printf("该迷宫路径如下：\n");
for(k=0;k<=st.top;k++)
{
printf("\t(%d,%d)",st.data[k].i,st.data[k].j);
if((k+1)%5==0)
printf("\n");
}
printf("\n");
return true;
}
find=0;
while(di<4&&find==0) //向未搜索过的方位搜索
{
di++;
switch(di)
{
case 0:i=st.data[st.top].i-1;
j=st.data[st.top].j; break; //向上走
case 1:i=st.data[st.top].i;
j=st.data[st.top].j+1; break; //向右走
case 2:i=st.data[st.top].i+1;
j=st.data[st.top].j; break; //向下走
case 3:i=st.data[st.top].i;
j=st.data[st.top].j-1; break; //向左走
}
if(mg[i][j]==0) find=1;
}
if(find==1) //find==1 说明有可行下一步
{
st.data[st.top].di=di;
st.top++;
st.data[st.top].i=i;//进栈
st.data[st.top].j=j;
st.data[st.top].di=-1;
mg[i][j]=-1;
}
else //没有可行下一步，则返回上一步，继续搜索{
mg[st.data[st.top].i][st.data[st.top].j]=0;
st.top--;
}
}
return false;
}
5.主函数：
int i,j;
int M,N; //迷宫大小
int X,Y; //出口
cout<<"请输入迷宫大小：行列数"<<endl;
cin>>M>>N;
cout<<"该迷宫出口位置："<<endl;
cin>>X>>Y;
for(i=0;i<=M+1;i++) mg[i][0]=mg[i][M+1]=1; //初始化边框
for(j=0;j<=N+1;j++) mg[0][j]=mg[N+1][j]=1;
cout<<"请输入迷宫布置，0，1分别表示迷宫中的通路和障碍："<<endl;
for(i=1;i<=M;i++) //输入迷宫
{
for(j=1;j<=N;j++)
{
cin>>mg[i][j];
}
}
if(!mgpath(1,1,M,N)) //如果返回值为false，则迷宫无解
printf("该迷宫问题没有解！\n");
return 0;
}
四、调试分析
五、用户使用说明
1.点击运行程序:迷宫问题.cpp；
2.屏幕显示：请输入迷宫大小：行列数；
3.输入行列数，以空格键隔开，Enter键返回；
4.屏幕显示：该迷宫出口位置；
5.用户键盘输入迷宫出口位置坐标，Enter键返回。
6．若迷宫有解，屏幕输出成功路径；若该迷宫无解，屏幕输出“该迷宫问题没有解！”。
六、测试结果
三组测试结果如下：
1．
2.
3.
实验成功！。
