迷宫C++源代码

#include <iostream.h> #include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR 0 #define OVERFLOW 0 struct PosType {int x; int y; }; #define N 50 typedef int MazeType[N][N]; MazeType m; int x,y; PosType begin,end; void Print() {int i,j; for (i=0;i<x;i++) {for (j=0;j<y;j++) cout<<m[i][j]<<" "; cout<<endl; } } void Init (int k) { int i, j,x1,y1; cout<<"请输入迷宫的行数,列数(包括外墙):"<<"\n"; cin>>x>>y; for(i=0;i<y;i++) {m[0][i]=0; m[x-1][i]=0; } for(i=0;i<x-1;i++) {m[i][0]=0; m[i][y-1]=0; } for(i=1;i<x-1;i++) for(j=1;j<y-1;j++) m[i][j]=k; cout<<"请输入迷宫内墙单元数:"<<"\n"; cin>>j; cout<<"请依次输入迷宫内墙每个单元的行数,列数:"<<"\n"; for(i=1;i<=j;i++) {cin>>x1>>y1; m[x1][y1]=0; } cout<<"迷宫的结构如下:"<<"\n"; Print(); cout<<"请输入入口的行数,列数:"<<"\n"; cin>>begin.x>>begin.y; cout<<"请输入出口的行数,列数:"<<"\n"; cin>>end.x>>end.y; } int curstep=1; struct SElemType {int ord; PosType seat; int di; }; #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct{ SElemType *base; SElemType *top; int stacksize; }SqStack; bool InitStack (SqStack &S) {S.base =(SElemType *)malloc (STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base ) exit (OVERFLOW); S.top=S.base; S.stacksize =STACK_INIT_SIZE; return OK; } void DestroyStack (SqStack &S); void ClearStack (SqStack &S); bool StackEmpty (SqStack S) { if(S.top ==S.base) return true; else return false; } int StackLength(SqStack S); void GetTop(SqStack S,SElemType &e); bool Push(SqStack &S,SElemType e) {if(S.top-S.base>=S.stacksize ) {S.base =(SElemType *) realloc (S.base ,(S.stacksize +STACKINCREMENT)*sizeof (SElemType)); if(!S.base ) exit (OVERFLOW); S.top =S.base+S.stacksize ; S.stacksize +=STACKINCREMENT; } *(S.top) ++=e; return OK; } bool Pop(SqStack &S,SElemType &e) {if (S.top==S.base) return ERROR; e=*--(S.top); return OK; } void StackTraverse(SqStack S,void (*visit)(SElemType)); void FootPrint (PosType a ) { m[a.x][a.y]=curstep;//使a点变为足迹curstep } bool Pass(PosType b)//当b点的值对应为1则可通，返回OK，反之，返回ERROR { if(m[b.x][b.y]==1) return OK; else return ERROR; } void NextPos (PosType &c,int di) {PosType direc[4]={{0,1},{1,0},{0,-1},{-1,0}};//行增量列增量，方向为东、南、西、北 c.x+=direc[di].x; c.y+=direc[di].y; } void MarkPrint (PosType b)//将b点赋值为-1，代表该点不通 {m[b.x][b.y]=-1;} bool MazePath(PosType start,PosType end)//若从start到end有通路，则求出一条放入栈中，并返回ture,否则返回false {SqStack S;//顺序栈 PosType curpos;//当前位置 SElemType e;//栈元素 InitStack(S);//初始栈 curpos=start;//当前位置在入口 do { if(Pass(curpos))//未走过 { FootPrint(curpos);//留足迹 e.ord=curstep; e.seat=curpos; e.di=0; Push(S,e);//入栈当前位置及状态 curstep++;//足迹加1 if(curpos.x==end.x&&curpos.y==end.y)//到出口 return true; NextPos(curpos,e.di);//下一个方向 } else {//不通 if(!StackEmpty(S))//栈不空 { Pop(S,e);//退到前一个位置 curstep--; while ((e.di==3)&&(!StackEmpty(S)))//前一位置是北方 {MarkPrint(e.seat);//设为不通 Pop(S,e);//再退一步 curstep--; } if(e.di<3)//方向不是北 {e.di++; Push(S,e); curstep++; curpos=e.seat; NextPos(curpos,e.di); } } } }while(!StackEmpty(S)); return false; } void main() {Init(1); if (MazePath(begin,end)) {cout<<"此迷宫从入口到出口的路径如下:"<<"\n"; Print(); } else cout<<"此迷宫没有从入口到出口的路径:"<<"\n"; }