《可连通迷宫程序.doc》由会员分享，可在线阅读，更多相关《可连通迷宫程序.doc（10页珍藏版）》请在金锄头文库上搜索。
1、#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 ; /临近的四个方向
2、，表示和某点周围的横纵坐标差值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时，为了增加难度，如果产生的起点和终点
3、在同一行，则重新产生。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.e
4、mpty() ) 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 ( maptem
5、p1.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;/根据难度设置不同的通路与墙的比例/i
6、nt 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
7、,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:/向北寻（）ReturnP
8、os.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
9、(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;/标志el
10、seif(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.rmi
11、d.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)
