《迷宫求解参考答案》由会员分享，可在线阅读，更多相关《迷宫求解参考答案（5页珍藏版）》请在金锄头文库上搜索。
1、#include#include#include#include#include/函数状态码定义#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define NULL 0 /墙或通路及前进方向符号定义#define WALL 0 /代表当前格子是墙#define PATH 1 /代表是通路且未走过#define RIGHT -1 /代表是通路且从其向右走#define DOWN -2 /代表是通路且从其向下走#define LEFT -3 /代表是通路且从其向左走#define UP -
2、4 /代表是通路且从其向上走#define BACK -5 /代表是通路且从其后退一步#define DESTINATION -6 /代表当前格子是通路且是目标位置typedef int MazeType1010; /最外凿初始化成墙，实际含*8个格子typedef int Status;typedef int ElemType; /迷宫数组中的元素类型/栈的定义和实现，采用顺序存储结构/#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef structint x;int y;PosType;/迷宫中坐标的位置typedef s
3、tructint ord;PosType seat;int di;SElemType;/栈中元素类型typedef structSElemType *base;SElemType *top;int stacksize;Stack;/栈类型Status InitStack(Stack if(!S.base) exit(OVERFLOW); /存储分配失败S.top=S.base; /空栈S.stacksize=STACK_INIT_SIZE;return OK;/InitStackStatus Push(Stack if(!S.base) exit(OVERFLOW);S.top=(S.base
4、+S.stacksize);/使得S.top重新指向原栈顶,因reallocS.stacksize+=STACK_INIT_SIZE;*S.top+=e; /top指向待插入位置 return OK;/PushStatus Pop(Stack elsee=*(-S.top); /栈顶元素为*(S.top-1)return OK;Status GetTop(Stack S,SElemType e=*(S.top-1); /注意top指向待插入位置return OK;Status StackEmpty(Stack S)/判空if(S.top=S.base)return TRUE;else retu
5、rn FALSE;/StackEmptyStatus StackTraverse(Stack S,Status (*visit)(SElemType)/从栈底元素到栈顶元素依次执行visit函数，通常用于输出栈中元素SElemType *p=S.base;if(S.base=S.top)printf(“空栈n“);elsewhile(pS.top)(*visit)(*p);+p;return OK;Status PrintSElem(SElemType e)printf(“step:%d to (%d,%d)n“,e.ord,e.seat.x,e.seat.y);return OK;/迷宫求解
6、的具体算法-/Status MakeMaze(MazeType srand(time(NULL);for(m.y=0;m.y=9;m.y+)maze0m.y=WALL;maze9m.y=WALL;for(m.x=1;m.x=8;m.x+) mazem.x0=WALL;mazem.x9=WALL;for(m.x=1;m.x=8;m.x+)for(m.y=1;m.y=8;m.y+)mazem.xm.y=rand()%2;return OK;/MakeMazevoid PrintMaze(MazeType maze)int x,y;for(x=0;x=9;x+)for(y=0;y=9;y+)swit
7、ch(mazexy)case WALL:printf(“);break;case PATH:printf(“ “);break;case RIGHT:printf(“);break;case DOWN: printf(“);break;case LEFT: printf(“);break;case UP: printf(“);break;case BACK: printf(“ “);break;case DESTINATION:printf(“);break;default:printf(“errorn“);exit(-1);printf(“n“);PosType Nextpos(PosTyp
8、e position,ElemType direction)PosType result;result=position;switch (direction)case 1:result.y+;break;case 2:result.x+;break;case 3:result.y-;break;case 4:result.x-;break;return result;Status PassMaze(MazeType SElemType e;int curstep=1;curpos=start;if(mazecurpos.xcurpos.y!=PATH) printf(“当前迷宫没有入口n“);
9、 return FALSE;do if(mazecurpos.xcurpos.y=PATH)/当前位置可通e.ord=curstep;e.seat=curpos;e.di=1;Push(S,e);if(curpos.x=end.xreturn OK;else mazecurpos.xcurpos.y=RIGHT;/从其向右走curpos=Nextpos(curpos,1);curstep+;else/当前位置不通GetTop(S,e);while(!StackEmpty(S)Pop(S,e);curstep-;if(StackEmpty(S)break;GetTop(S,e);if(e.di4
10、) /栈顶位置有其他方向可以选择Pop(S,e); e.di+; Push(S,e);mazee.seat.xe.seat.y=-e.di; /注意前进方向踪迹与e.di互为相反数curpos=Nextpos(e.seat,e.di);while(!StackEmpty(S);return FALSE;void main()MazeType maze;PosType start,end;Stack S;InitStack(S);MakeMaze(maze);printf(“初始迷宫为：n“);PrintMaze(maze);printf(“输入迷宫的入口位置坐标从(0,0)到(9,9): “);scanf(“%d,%d“,printf(“输入迷宫的出口位置坐标从(0,0)到(9,9): “);scanf(“%d,%d“,if(PassMaze(maze,start,end,S)printf(“迷宫可通,路径踪迹如下:n“);PrintMaze(maze);printf(“具体路径为：n“);StackTraverse(S,PrintSElem);elseprintf(“迷宫不可通,路径踪迹如下:n“);PrintMaze(maze);printf(“-输入任意数字键结束-“);int pause;scanf(“%d“,
