#include
typedef enum { ERROR, OK } Status; typedef struct { int row; //row表示\行\号 int line; //line表示\列\号 }PosType; //位置的元素类型
typedef struct{ int ord; //该通道在路径上的\序号\ PosType seat; //通道块在迷宫中的\坐标位置\ int di; //从此通道走向下以通道块的\方向\}SelemType; //栈的元素类型
typedef struct{ SelemType * base; SelemType * top; int stacksize; }SqStack;
/*创建一个空栈S*/
Status InitStack(SqStack &S) { S.base=(SelemType *)malloc(100*sizeof(SelemType)); if(!S.base) return ERROR; S.top=S.base; S.stacksize=100; return OK;
} /*插入新元素a*/
Status Push(SqStack &S,SelemType &a) { *S.top++=a; return OK; } /*删除栈顶元素，a返回其值*/
Status Pop(SqStack &S,SelemType &a) { if(S.top==S.base)return ERROR; a=*--S.top; return OK;
} /*检查是否空栈*/
Status StackEmpty(SqStack S)
{ if(S.top==S.base)return OK; else return ERROR; }
void Initmaze(int maze[12][12],int size) { char select; printf(\选择创建方式 A:自动生成 B:手动创建\\n\ label:scanf(\ if(select=='a'||select=='A') //自动生成 { for(int i=0;i void printmaze(int maze[12][12],int size) { printf(\ printf(\显示所建的迷宫(#表示外面的墙):\\n\ for(int i=0;i printf(\ printf(\ for(i=1;i } /*输出路径*/ void printpath(int maze[12][12],SqStack S,int size) { printf(\通路路径为:\\n\ SelemType *p=S.base; while(p!=S.top) { maze[p->seat.row][p->seat.line]=2; //标记为路径中的点 p++; } for(int i=0;i Status Pass(int maze[12][12],PosType CurPos) { if (maze[CurPos.row][CurPos.line]==0) return OK; // 如果当前位置是可以通过，返回1 else return ERROR; // 其它情况返回0 } /*标记当前位置不可通*/ void Markfoot(int maze[12][12],PosType CurPos) { maze[CurPos.row][CurPos.line]=1; } /*进入下一位置*/ PosType NextPos(PosType CurPos, int Dir) { PosType ReturnPos; switch (Dir) { case 1: //下一模块为东临模块 ReturnPos.row=CurPos.row; ReturnPos.line=CurPos.line+1; break; case 2: //下一模块为南临模块 ReturnPos.row=CurPos.row+1; ReturnPos.line=CurPos.line; break; case 3: //下一模块为西临模块 ReturnPos.row=CurPos.row; ReturnPos.line=CurPos.line-1; break; case 4: //下一模块为北临模块 ReturnPos.row=CurPos.row-1; ReturnPos.line=CurPos.line; break; } return ReturnPos; } /*若迷宫maze中从入口 start到出口 end的通道，则求得一条存放在栈中 Status MazePath(int maze[12][12],SqStack &S, PosType start, PosType end) { PosType curpos; int curstep; SelemType e; InitStack(S); */ curpos = start; // 设定\当前位置\为\入口位置 curstep = 1; // 探索第一步 do { if (Pass(maze,curpos)) // 当前位置可通过，即是未曾走到过的通道块 { Markfoot(maze,curpos); // 留下足迹 e.di =1; e.ord = curstep; e.seat= curpos; Push(S,e); // 加入路径 if (curpos.row==end.row && curpos.line==end.line) return OK; // 到达终点（出口） curpos = NextPos(curpos, 1); // 下一位置是当前位置的东邻 curstep++; // 探索下一步 } else // 当前位置不能通过 { if (!StackEmpty(S)) { Pop(S,e); while(e.di==4&&!StackEmpty(S)) { Markfoot(maze,e.seat); // 留下不能通过的标记，并退回一步 Pop(S,e); } if (e.di<4) { e.di++; // 换下一个方向探索 Push(S, e); curpos = NextPos(e.seat, e.di); // 当前位置设为新方向的相邻块 } } } }while (!StackEmpty(S)); return ERROR; } void main () { SqStack S; int size=0; //正方形迷宫尺寸 int maze[12][12]; //存储迷宫内路径可通情况 for(int n=0;n<10;n++) { printf(\创建一个正方形迷宫，请输入迷宫尺寸(注意不要大于10):\\n\设置迷宫大小 scanf(\ if(size<1 || size>10) { printf(\输入错误!\ return; } Initmaze(maze,size); //初始化迷宫 printmaze(maze,size); //显示所创建的迷宫 PosType start,end; //设置入口和出口 printf(\输入入口行坐标和列坐标:\ scanf(\ scanf(\ printf(\输入出口行坐标和列坐标:\ scanf(\ scanf(\ if(MazePath(maze,S,start,end)) //若有通路，显示通路 printpath(maze,S,size); else printf(\找不到通路!\\n\\n\ } }