2022年迷宫程序 2.pdf

#include #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) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 6 页 - - - - - - - - - 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 maze1212,int size) char select; printf(选择创建方式A:自动生成B:手动创建 n); label:scanf(%c,&select); if(select=a|select=A) /自动生成 for(int i=0;isize+2;i+)maze0i=1; for( i=1;isize+1;i+) mazei0=1; for(int j=1;jsize+1;j+) mazeij=rand()%2; mazeisize+1=1; for(i=0;isize+2;i+)mazesize+1i=1; else if (select=b|select=B) /手动设置 printf( 按行输入 %d*%d 数据,0代表可通 ,1 代表不可通 (每行以 Enter结束):n,size,size); for(int i=0;isize+2;i+)maze0i=1; for( i=1;isize+1;i+) mazei0=1; for(int j=1;jsize+1;j+) scanf(%d,&mazeij); mazeisize+1=1; for(i=0;isize+2;i+)mazesize+1i=1; else if(select=n) goto label; /排除 Enter 键的影响else printf(输入错误 !); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 6 页 - - - - - - - - - /*显示迷宫 */ void printmaze(int maze1212,int size) printf(nn); printf(显示所建的迷宫 (#表示外面的墙 ):n); for(int i=0;isize+2;i+) printf(%c ,#); printf(n); for(i=1;isize+1;i+) printf(%c ,#); for(int j=1;jsize+1;j+) printf(%d ,mazeij); printf(%c,#); printf(n); for(i=0;iseat.rowp-seat.line=2; /标记为路径中的点p+; for(int i=0;isize+2;i+) printf(%c ,#);printf(n); for(i=1;isize+1;i+) printf(%c ,#); for(int j=1;jsize+1;j+) if(mazeij=2) printf(%c ,0); else printf( ); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 6 页 - - - - - - - - - printf(%c,#); printf(n); for(i=0;isize+2;i+) printf(%c ,#);printf(nn); /*判断当前位置是否可通 */ Status Pass(int maze1212,PosType CurPos) if (mazeCurPos.rowCurPos.line=0) return OK; / 如果当前位置是可以通过，返回1 else return ERROR; / 其它情况返回 0 /*标记当前位置不可通 */ void Markfoot(int maze1212,PosType CurPos) mazeCurPos.rowCurPos.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 的通道，则求得一条存放在栈中名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 6 页 - - - - - - - - - */ Status MazePath(int maze1212,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.di4) e.di+; / 换下一个方向探索Push(S, e); curpos = NextPos(e.seat, e.di); / 当前位置设为新方向的相邻块 while (!StackEmpty(S); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - return ERROR; void main () SqStack S; int size=0; /正方形迷宫尺寸int maze1212; /存储迷宫内路径可通情况for(int n=0;n10;n+) printf( 创建一个正方形迷宫，请输入迷宫尺寸(注意不要大于10):n); /设置迷宫大小scanf(%d,&size); if(size10) printf( 输入错误 !); return; Initmaze(maze,size); /初始化迷宫printmaze(maze,size); /显示所创建的迷宫PosType start,end; /设置入口和出口printf( 输入入口行坐标和列坐标:); scanf(%d,&start.row); scanf(%d,&start.line); printf( 输入出口行坐标和列坐标:); scanf(%d,&end.row); scanf(%d,&end.line); if(MazePath(maze,S,start,end) /若有通路，显示通路printpath(maze,S,size); else printf( 找不到通路 !nn); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -