可连通迷宫程序.doc

#include stdafx.h#include #include #include #include #include #include #include #define M 20#define N 20using namespace std;/曝光命名空间typedef structint r;/通道块的行坐标rowint c;/通道块的列坐标colint di;/走向下一通道块的方向directionint ord;/当前路径的序列号orderPosType,Stack;/栈记录通道块的各元素int dir42 = -1, 0, 1, 0, 0, -1, 0, 1 ; /临近的四个方向，表示和某点周围的横纵坐标差值void InitStartEnd(PosType* start,PosType* end, int degree)start-r=rand()%(M-3)+1;/随机入口从1-（M-3）start-c=0;start-di=1;start-ord=0;/随机入口end-r=rand()%(M-3)+1;/随机出口从1-（M-3）end-c=N-1;/随机出口if ( degree 1 & abs(end-r - start-r) 8) InitStartEnd( start, end, degree );/当难度为2、3、4时，为了增加难度，如果产生的起点和终点在同一行，则重新产生。void CreateWell( char MazeMN, PosType start, PosType end, int degree ) int i, j;Mazestart.rstart.c=s;/设置起点Mazeend.rend.c=e;/设置终点start.c +;end.c -;queue Q;Q.push( start );Mazestart.rstart.c = ;bool flag4;PosType temp, temp1, fatherMN;bool mapMN;memset( map, true, sizeof(map) );while ( !Q.empty() ) temp = Q.front();Q.pop();if ( temp.c = end.c & temp.r = end.r ) break;int t = 0;memset( flag, true, sizeof(flag) );while ( t != 4 ) i = rand() % 4;if ( !flagi ) continue;t+;flagi = false;temp1 = temp;temp1.r += diri0;temp1.c += diri1;if ( temp1.r = M-1 | temp1.c = N-1 ) continue;if ( maptemp1.rtemp1.c = false ) continue;maptemp1.rtemp1.c = false;Q.push( temp1 );fathertemp1.rtemp1.c.c = temp.c;fathertemp1.rtemp1.c.r = temp.r;int x, y;/打通通路while ( temp.c != start.c | temp.r != start.r ) Mazetemp.rtemp.c = ;x = temp.r;y = temp.c;temp.r = fatherxy.r;temp.c = fatherxy.c;/根据难度设置不同的通路与墙的比例/int u=1;switch ( degree ) case 1: u = N*M/1; break;case 2: u = N*M/2; break;case 3: u = N*M/4; break;case 4: u = N*M/7; break;default: printf(输入错误, 进入默认难度1);break;int t;while ( u != 0 ) i = rand()%(N-2)+1;j = rand()%(N-2)+1;if ( Mazeij != ) Mazeij= ;/随机产生迷宫空格u-;void InitMaze(char MazeMN,PosType start,PosType end, int degree)int i,j;for(i=0;iM;i+)for(j=0;jN;j+)Mazeij=#;/初始化迷宫矩阵全部为墙CreateWell( Maze, start, end, degree );/对迷宫内部的可行路径的设置PosType NextPos(PosType test, int di)/求下一个探索的目标,方向先（）后（）PosType ReturnPos; switch (di)case 1:/向东寻（）ReturnPos.r=test.r;ReturnPos.c=test.c+1;break;case 2:/向北寻（）ReturnPos.r=test.r-1;ReturnPos.c=test.c;break;case 3:/向南寻（）ReturnPos.r=test.r+1;ReturnPos.c=test.c;break;case 4:/向西寻（）ReturnPos.r=test.r;ReturnPos.c=test.c-1;break;ReturnPos.di=1;ReturnPos.ord=0;return ReturnPos;void Renew(char MazeMN,Stack SN*M,int first,int last)int i,j;for(i=1;iM-1;i+)for(j=1;jN-1;j+)if(Mazeij=!)Mazeij= ;while(first!=last-1) first+;MazeSfirst.rSfirst.c= ;Sfirst.r=Sfirst.c=0;/再此寻找路径时，从栈first开始到last寻找到迷宫中的位置/删除栈Sfirst到Slast间存储迷宫路径的节点Maze00=#;void Pathflag(char MazeMN,PosType pre,PosType mid,PosType next)if(pre.r=next.r) Mazemid.rmid.c=1;/标志elseif(pre.c=next.c) Mazemid.rmid.c=2;/标志elseif(next.r=pre.r+1)if(next.c=pre.c-1)if(next.c=mid.c) Mazemid.rmid.c=3;/标志else Mazemid.rmid.c=6;/标志else if(next.c=mid.c) Mazemid.rmid.c=4;/标志else Mazemid.rmid.c=5;/标志elseif(next.c=pre.c+1)if(next.r=mid.r) Mazemid.rmid.c=3;else Mazemid.rmid.c=6;else if(next.r=mid.r) Mazemid.rmid.c=4;else Mazemid.rmid.c=5;void PrintPath(Stack SN*M,int top)int i=0;while(i4) return 0;/当方向数累加到4个以上时,就退出,说明无方向可走了if(top!=-1) top-;S+top=start;/把入口压栈test=NextPos(start, start.di); / 设定当前测试位置为入口的东面通道块while (top=0)if(Mazetest.rtest.c= |Mazetest.rtest.c=e)S+top=test;Stop.ord=top;/加入路径if(top=2)Pathflag(Maze,Stop-2,Stop-1,Stop);/ 留下不同的足迹if(test.r=end.r&test.c=end.c) SN*M-1.ord=top;/用栈的最后一个单元的路径数来表示栈顶标志return top-1;/返回路径的步数/ 到达终点（出口）并输出路径步数test=NextPos(Stop,Stop.di); / 下一位置是当前位置的东邻else / 当前位置不能通过if(Stop.r=start.r&Stop.c=start.c)start.di+;/当退回到开始处时，将开始通道块的不可通的方向+1if(top=0|start.di4)/退到入口或开始处,没有方向可行时,就说明无路径可走SN*M-1.ord=top+1;/当start.di=4时，记录栈顶+1break;/当退到入口或开始处没有方向可行时，就说明无路径可走/无路径可走，直接就跳出循环if (Stop.di4) Stop.di+;test=NextPos(Stop,Stop.di);/ 当前位置设为新方向的相邻块(有四种方案可供选择) / ifelseMazeStop.rStop.c=!;Stop.ord=0;top-;/ 留下不能通过的标记，并退回一步 / else / elsestart.ord=0;return 0; / MazePathvoid PrintMaze(char MazeMN)/打印迷宫int i,j;for(i=-1;iM;i+)if(i=-1)printf(t );elseprintf(t%5d,i);/打印出行序列号for(j=0;jN;j+)if(i=-1) printf(%2d,j);/打印出列序列号elseswitch(Mazeij)case s :printf(入);break;case e :printf(出);break;case # :printf();break;case ! :printf( );break;case :printf( );break;case 1 :printf();break;case 2 :printf();break;case 3 :printf();break;case 4 :printf();break;case 5 :printf();break;case 6 :printf();break;printf(n);void PrintMaze1(char MazeMN)/打印迷宫int i,j;for(i=-1;iM;i+)if(i=-1)printf( );elseprintf(%5d,i);for(j=0;jN;j+)if(i=-1) printf(%2d,j);elseprintf(%c,Mazeij);printf(n);void main()DWORD starttime,midtime,endtime;char MazeMN;/迷宫PosType start,end;/起点与终点int degree;Stack SN*M;/栈int top=-1;/用栈的最后一个单元的路径数来表示栈顶标志int path=0,testcase=1;/path是记录路径的步数，testcase是记录迷宫的第一步选走方案int first=0,last=0;/在寻求其他路径时用first表示路径开始处，last表示路径结束处，first-last间的路径要消去int i=0,minpath=N*M,minpathcaseN*M/3;/记录最小路径minpath和其方案号序列isystem(title 可连通迷宫算法设计及实现);printf(n*n);printf(tttHELLO ：Welcome To the Maze Gamenn);printf(ttt学 校：西安建筑科技大学华清学院nn);printf(ttt题 目：可连通迷宫算法设计及实现nn);printf(ttt专业班级： 电子信息科学与技术0701 nn);printf(ttt学 生：t XXXXXXnn);printf(ttt指导老师：t XXXXXXnn);printf(n*n);doprintf(请按“enter”键开始算法的演示:n);getchar();printf( 选择迷宫难度等级(1最简单，4最难)：1, 2, 3, 4nn );scanf( %d, °ree );testcase=1;first=last=0;i=0;minpath=N*M; printf(n*n);srand(unsigned int)time(NULL);struct tm *newtime; /开始初始化迷宫 starttime = GetTickCount();InitStartEnd(&start,&end, degree);/随机初始化入口和出口InitMaze(Maze,start,end, degree);/随机初始化迷宫/成功初始化迷宫MazePath(Maze,start,end,S,top);midtime = GetTickCount();printf(n系统完全随机到的迷宫图如下：nn);Renew(Maze,S,start.ord,SN*M-1.ord);/复原迷宫PrintMaze(Maze);printf(n初始化迷宫时间为 %d 毫秒n,midtime-starttime);printf(n*n);printf(请按“enter”键系统自动寻找路径：);getchar();getchar(); midtime = GetTickCount();while(testcase) path=MazePath(Maze,start,end,S,top