漫步迷宫非邻接表型c.docx

/文件格式为.c#include #include #include #include #define MAX 20typedef structint row,col;int roadMAXMAX; /存储矩阵 1为墙 0为空int start_row; int start_col;/进口坐标int end_row;int end_col;/出口坐标int dingdiannum; ROAD;typedef structint entry,exit;/进出口编号int recordMAX*MAX; int queueMAX*MAX;/存储广度优先搜索访问到的顶点int visitedMAX*MAX; /*用visited数组标记图的结点是否遍历过*/SPARE;ROAD InPut(ROAD R)/手动输入迷宫/迷宫矩阵int i,j;printf(请输入迷宫的规格:n);printf( 行数= );scanf(%d,&R.row);printf( 列数= );scanf(%d,&R.col);R.dingdiannum=R.col*R.row; printf(顶点数为:%dn,R.dingdiannum);for(i=0;iR.row;i+)printf(输入 %d行 :%d ,i+1,i+1);for(j=0;j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17n); for(y=0;y=R.row;y+)printf(第%d行为 :,y+1);for(x=0;x=R.col;x+)printf(%d ,R.roadyx);printf(n);printf(列数为: %d 行数为: %d,R.col+1,R.row+1);R.dingdiannum=(R.col+1)*(R.row+1);printf(顶点数为:%dn,R.dingdiannum);getchar();return R;ROAD RoadAuto(ROAD R)/随机构建迷宫矩阵int b,x,y;srand(int)time(NULL);b=12+(int)(6.0*rand()/(RAND_MAX+1.0);R.col=9+(int)(8.0*rand()/(RAND_MAX+1.0);/列数9=row=17R.row=6+(int)(3.0*rand()/(RAND_MAX+1.0);/行数6=col=10for(y=0;y=R.row;y+)for(x=0;xR.col;x+)if(x=0|y=0|y=R.row)R.roadyx=1;/加围墙elseR.roadyx=(int)(2.0*rand()/(RAND_MAX+1.0);R.roadyx=1;/加围墙R=PrintfRoad(R);return R;SPARE Seekpass(ROAD R,SPARE S)/广度优先收索思想,寻找到出口的路径int i,x,y,front=0,rear=1;S.entry=(R.start_row-1)*R.col+R.start_col-1;S.exit=(R.end_row-1)*R.col+R.end_col-1;for(i=0;iR.dingdiannum;i+)S.recordi=-1;/初始化S.visitedi=0;/初始化S.queuerear=S.entry;/第一个探索顶点入队,存储顶点编号S.visitedS.entry=1;/标示被访问while(front!=rear)x=S.queuefront+1%R.col;/将编号转换为坐标y=S.queuefront+1/R.col;if(S.visitedy*R.col+x+1=0&x+1R.col&R.roadyx+1=0)/向右S.visitedy*R.col+x+1=1;S.recordy*R.col+x+1=S.queuefront+1;/以与坐标为的顶点相邻的坐标顶点编号为下表存储坐标的编号S.queue+rear=y*R.col+x+1;if(y*R.col+x+1)=S.exit)return S;if(S.visited(y+1)*R.col+x=0&y+10&R.roadyx-1=0)/向左S.visitedy*R.col+x-1=1;S.recordy*R.col+x-1=S.queuefront+1;S.queue+rear=y*R.col+x-1;if(y*R.col+x-1)=S.exit)return S;if(S.visited(y-1)*R.col+x=0&y0&R.roady-1x=0)/向上S.visited(y-1)*R.col+x=1;S.record(y-1)*R.col+x=S.queuefront+1;S.queue+rear=(y-1)*R.col+x;if(y-1)*R.col+x)=S.exit)return S;front=front+1;return S;void OutPut(int col,SPARE S) int i=0,t; if(S.entry=S.exit)printf(已在出口n); elseif(S.recordS.exit!=-1)t=S.exit;printf(最短路径为:n); while(t!=S.entry)printf(%d,%d-,t/col+1,t%col+1); t=S.recordt; if(+i%5=0)printf(n); printf(%d,%d,t/col+1,t%col+1); elseprintf(实在找不到走出去的路径n);printf(n);ROAD Meunchooce(ROAD R)int a;char ch=y;printf(n*n);printf( 1.手动输入迷宫矩阵n);printf( 2.调用随机函数构建迷宫矩阵n);printf( 3.退出n);printf( 请问您想怎样构建这个迷宫矩阵.n);doprintf( 输入1-3的数字!.n);scanf(%d,&a);switch(a)case 1:R=InPut(R);break;/手动构建迷宫case 2:doprintf(nnn);R=RoadAuto(R);printf(是否重新构建迷宫y/n: );ch=getchar();while(ch=y|ch=Y);return R;break;/随机产生迷宫case 3:exit(0);while(a3);return R;main()int x;ROAD R;SPARE S;system(color 9e);/*窗口颜色函数*/R=Meunchooce(R);/菜单项,选择以怎样的方式构建迷宫printf(输入人口坐标: );scanf(%d,%d,&R.s