完整word版实验报告迷宫问题Word文档格式.docx
- 文档编号:5111640
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:10
- 大小:50.04KB
完整word版实验报告迷宫问题Word文档格式.docx
《完整word版实验报告迷宫问题Word文档格式.docx》由会员分享,可在线阅读,更多相关《完整word版实验报告迷宫问题Word文档格式.docx(10页珍藏版)》请在冰点文库上搜索。
计算机解迷宫通常用的是“穷举求解”方法,即从入口出发,顺着某一个方向进行探索,若能走通,则继续往前进;
否则沿原路退回,换一个方向再继续探索,直至所有可能的通路都探索到为止,如果所有可能的通路都试探过,还是不能走到终点,那就说明该迷宫不存在从起点到终点的通道,可以二维数组存储迷宫数据。
[程序实现]
#include<
stdio.h>
stdlib.h>
//1.迷宫位置坐标类型
typedefstruct
{
intx;
//行
inty;
//列
}PosType;
#defineMAXENGTH25//迷宫最大行列数位25
typedefintMazeType[MAXENGTH][MAXENGTH];
//迷宫数列
typedefstruct//定义栈
intord;
//通道块在路径上的序号
PosTypeseat;
//通道块在迷宫中的位置
intdi;
//走向下一块的方向(0~3表示东、南、西、北)
}SElemType;
//2.全局变量
MazeTypem;
//迷宫数组
intcurstep=1;
//当前位置,初值为1
#defineSTACK_INIT_SIZE10//存储空间初始分配量
#defineSTACKINCREMENT2//存储空间分配增量
//3.栈的顺序存储表示
typedefstructSqStack
SElemType*base;
//尾指针
SElemType*top;
//头指针
intstacksize;
//栈大小
}SqStack;
//顺序表
//4.构造空栈
intInitStack(SqStack&
S)
S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!
(S.base))
exit(0);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return1;
}
//5.判断栈是否为空(用来判断迷宫是否不可达到出口)
intStackEmpty(SqStackS)
if(S.top==S.base)//栈底与栈顶相等为空栈
return1;
else
return0;
//6.插入元素
intPush(SqStack&
S,SElemTypee)
if(S.top-S.base>
=S.stacksize)//栈顶-栈底>
=栈长,说明空间已满
{
S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!
S.base)
exit(0);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*(S.top)++=e;
//7.栈不为空时,删除栈顶元素,用e返回(用于当栈顶元素各方向均不通时,将其从路径中删除)
intPop(SqStack&
S,SElemType&
e)
if(S.top==S.base)
e=*--S.top;
//先将S.top的值赋给e,再将S.top向下移一位
//8.判断迷宫m中b点是否可通过(是1,否0),其中墙为0,可通过路径为1,不可通过路径为-1
intPass(PosTypeb)
if(m[b.x][b.y]==1)
//9.是迷宫m中a的序号变为足迹(即该位置目前可通过)
voidFootPrint(PosTypea)
m[a.x][a.y]=curstep;
//10.根据当前位置方向,返回下一位置
PosTypeNextPos(PosTypec,intdi)
PosTypedirec[4]={{0,1},{1,0},{0,-1},{-1,0}};
c.x+=direc[di].x;
c.y+=direc[di].y;
returnc;
//11.道路不能通过时(即为死路),将其标记为-1
voidMarkPrint(PosTypeb)
m[b.x][b.y]=-1;
//12.求迷宫出口
intMazePath(PosTypestart,PosTypeend)
SqStackS;
PosTypecurpos;
//当前位置
SElemTypee;
InitStack(S);
curpos=start;
do
if(Pass(curpos))
{
FootPrint(curpos);
e.ord=curstep;
e.seat.x=curpos.x;
e.seat.y=curpos.y;
e.di=0;
Push(S,e);
curstep++;
if(curpos.x==end.x&
&
curpos.y==end.y)
return1;
curpos=NextPos(curpos,e.di);
}
else
if(!
StackEmpty(S))
{
Pop(S,e);
curstep--;
while(e.di==3&
!
{
MarkPrint(e.seat);
Pop(S,e);
curstep--;
}
if(e.di<
3)
e.di++;
Push(S,e);
curstep++;
curpos=NextPos(e.seat,e.di);
}
}while(!
StackEmpty(S));
return0;
//13.输出迷宫结构
voidPrint(intx,inty)
inti,j;
for(i=0;
i<
x;
i++)
for(j=0;
j<
y;
j++)
printf("
%3d"
m[i][j]);
printf("
\n"
);
//14.主函数
intmain()
PosTypebegin,end;
inti,j,x,y,x1,y1;
printf("
请输入迷宫行列数(包括外墙):
(空格隔开)\n"
scanf("
%d%d"
&
x,&
y);
i++)//定义外墙
m[0][i]=0;
m[x-1][i]=0;
for(j=0;
y-1;
m[j][0]=0;
m[j][y-1]=0;
for(i=1;
x-1;
for(j=1;
m[i][j]=1;
//墙内初始值均为1
//输入迷宫中墙的个数
输入墙的个数:
"
%d"
j);
//安排墙的位置
请输入墙的位置(坐标),用空格隔开:
for(i=1;
=j;
scanf("
x1,&
y1);
m[x1][y1]=0;
迷宫结构如下\n"
Print(x,y);
请输入起点坐标:
scanf("
begin.x,&
begin.y);
请输入终点坐标:
end.x,&
end.y);
if(MazePath(begin,end))
此迷宫的一条路径如下:
Print(x,y);
此迷宫无法到达出口\n"
[实验结果]
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 完整 word 实验 报告 迷宫 问题