迷宫(C语言版)

/*注：本程序探索迷宫的优先顺序=1-下、2-右、3-上、4-左=总体趋势：下右，逆时针方向。因为出口就在右边下方*/#includestdio.h#includestdlib.h#includetime.h#definestack_init_size200#definestack_increment10#defineOVERFLOW0#defineOK1#defineERROE0#defineTRUE1#defineFALSE0typedefintStatus;typedefstruct{intx;inty;}PosType;typedefstruct{intord;//通道块在路径上的“序号”PosTypeseat;//通道块在迷宫中的“坐标位置”intdi;//从此通道块走向下一通道块的“方向”}SElemType;typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;intmg[20][20];/*随机生成迷宫的函数/*为了能够让尽量能通过，将能通过的块和不能通过的块数量比大致为2:1*/voidRandom(){inti,j,k;srand(time(NULL));mg[1][0]=mg[1][1]=mg[18][19]=0;//将入口、出口设置为“0”即可通过for(j=0;j20;j++)mg[0][j]=mg[19][j]=1;/*设置迷宫外围“不可走”，保证只有一个出口和入口*/for(i=2;i19;i++)mg[i][0]=mg[i-1][19]=1;/*设置迷宫外围“不可走”，保证只有一个出口和入口*/for(i=1;i19;i++)for(j=1;j19;j++){k=rand()%3;//随机生成0、1、2三个数if(k)mg[i][j]=0;else{if((i==1&&j==1)||(i==18&&j==18))/*因为距入口或出口一步的路是必经之路，故设该通道块为“0”加大迷宫能通行的概率*/mg[i][j]=0;elsemg[i][j]=1;}}}//构造一个空栈StatusInitStack(SqStack&s){s.base=(SElemType*)malloc(stack_init_size*sizeof(SElemType));if(!s.base)returnOVERFLOW;s.top=s.base;s.stacksize=stack_init_size;returnOK;}//当前块可否通过StatusPass(PosTypee){if(mg[e.x][e.y]==0)//0时可以通过returnOK;//如果当前位置是可以通过，返回1returnOVERFLOW;//其它情况返回0}//留下通过的足迹StatusFootPrint(PosTypee){mg[e.x][e.y]=7;returnOK;}//压入栈StatusPush(SqStack&s,SElemTypee){if(s.top-s.base=s.stacksize){s.base=(SElemType*)realloc(s.base,(s.stacksize+stack_increment)*sizeof(SElemType));if(!s.base)exit(OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=stack_increment;}*s.top++=e;returnOK;}//出栈StatusPop(SqStack&s,SElemType&e){if(s.top==s.base)returnERROE;e=*--s.top;returnOK;}//下一步PosTypeNextPos(PosType&e,intdir){PosTypeE;switch(dir){case1:E.x=e.x;//向下E.y=e.y+1;break;case2:E.x=e.x+1;//向右E.y=e.y;break;case3:E.x=e.x;//向上E.y=e.y-1;break;case4:E.x=e.x-1;//向左E.y=e.y;break;}returnE;}//是否空栈StatusStackEmpty(SqStacks){if(s.top==s.base)returnOK;returnOVERFLOW;}//留下不能通过的足迹StatusMarkPrint(PosTypee){mg[e.x][e.y]=3;returnOK;}//迷宫函数//若迷宫maze中从入口start到出口end的通道，则求得一条存放在栈中//（从栈底到栈顶），并返回TRUE；否则返回FALSEStatusMazePath(intmg,PosTypestart,PosTypeend,SqStack&s){PosTypecurpos;InitStack(s);SElemTypee;intcurstep;curpos=start;//设定当前位置为入口位置curstep=1;//探索第一步do{if(Pass(curpos)){//当前位置可通过，即是未曾走到过的通道块FootPrint(curpos);//留下足迹e.di=1;e.ord=curstep;e.seat=curpos;Push(s,e);//加入路径if(curpos.x==end.x&&curpos.y==end.y){printf(\n\n0∩_∩0能到达终点!);returnTRUE;}curpos=NextPos(curpos,1);//下一位置是当前位置的东邻curstep++;//探索下一步}else{//当前位置不能通过if(!StackEmpty(s)){Pop(s,e);while(e.di==4&&!StackEmpty(s)){MarkPrint(e.seat);Pop(s,e);}if(e.di4){e.di++;Push(s,e);//留下不能通过的标记，并退回一步curpos=NextPos(e.seat,e.di);/*当前位置设为新方向的相邻块*/}//if}//if}//else}while(!StackEmpty(s));printf(\n\n囧!不能到达终点!);returnFALSE;}//打印迷宫voidPrintMaze(){inti,j;printf(运行路径:\n\n);for(i=0;i20;i++){for(j=0;j20;j++){if(mg[i][j]==0)printf();elseif(mg[i][j]==1)printf(■);//迷宫的“墙”elseif(mg[i][j]==3)printf(◇);//不通的路elseif(mg[i][j]==7)printf(○);//通过的路径}printf(\n);}printf(\n);}voidmain(){SqStackS;PosTypestart,end;start.x=1;start.y=0;//起点坐标end.x=18;end.y=19;//终点坐标printf(\n==================迷宫游戏==================);printf(\n说明:■不能走的区域\t◇走不通的区域);printf(\n“空格”代表未到过的区域);printf(\n○代表能通过的路径，指向终点);printf(\n============================================);Random();printf(\n\nTest1:);MazePath(mg[20][20],start,end,S);PrintMaze();system(pause);Random();printf(\nTest2:);MazePath(mg[20][20],start,end,S);PrintMaze();system(pause);Random();printf(\nTest3:);MazePath(mg[20][20],start,end,S);PrintMaze();printf(\n==========程序退出，感谢使用!==========\n);}