迷宫问题参考模板

1、迷宫问题typedef int ElemType; /* 栈元素类型为整型 */typedef int Status;typedef int Boolean; #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0#includec3-1.h #includebo3-1.c/* c3-1.h 栈的顺序存储表示 */ #define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */ #define STACKINCREMENT 2 /* 存储空间分配增量 */ typedef struct SqStack Ele

2、mType *base; /* 在栈构造之前和销毁之后，base的值为NULL */ ElemType *top; /* 栈顶指针 */ int stacksize; /* 当前已分配的存储空间，以元素为单位 */ SqStack; /* 顺序栈 */* bo3-1.c 顺序栈的基本操作（9个） */ Status InitStack(SqStack *S)1 / 18 /* 构造一个空栈S */ (*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType); if(!(*S).base) exit(-1); /* 存储分配失败

3、*/ (*S).top=(*S).base; (*S).stacksize=STACK_INIT_SIZE; return OK; Status DestroyStack(SqStack *S) /* 销毁栈S，S不再存在 */ free(*S).base); (*S).base=NULL; (*S).top=NULL; (*S).stacksize=0; return OK; Status ClearStack(SqStack *S) /* 把S置为空栈 */ (*S).top=(*S).base; return OK; Status StackEmpty(SqStack S) /* 若栈S

4、为空栈，则返回TRUE，否则返回FALSE */ if(S.top=S.base) return TRUE; else return FALSE; int StackLength(SqStack S) /* 返回S的元素个数，即栈的长度 */ return S.top-S.base; Status GetTop(SqStack S,ElemType *e) /* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */ if(S.topS.base) *e=*(S.top-1); return OK; else return ERROR; Status Push(SqStack

5、*S,SElemType e) /* 插入元素e为新的栈顶元素 */ if(*S).top-(*S).base=(*S).stacksize) /* 栈满，追加存储空间 */ (*S).base=(SElemType *)realloc(*S).base,(*S).stacksize+STACKINCREMENT)*sizeof(ElemType); if(!(*S).base) exit(-1); /* 存储分配失败 */ (*S).top=(*S).base+(*S).stacksize; (*S).stacksize+=STACKINCREMENT; *(*S).top)+=e; ret

6、urn OK; Status Pop(SqStack *S,SElemType *e) /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */ if(*S).top=(*S).base) return ERROR; *e=*-(*S).top; return OK; Status StackTraverse(SqStack S,Status(*visit)(ElemType) /* 从栈底到栈顶依次对栈中每个元素调用函数visit()。 */ /* 一旦visit()失败，则操作失败 */ while(S.topS.base) visit(*S.base+);

7、printf(n); return OK; 一、非递归算法-利用栈求解迷宫问题（只输出一个解） */ typedef struct /* 迷宫坐标位置类型 */ int x; /* 行值 */ int y; /* 列值 */ PosType; #define MAXLENGTH 25 /* 设迷宫的最大行列为25 */ typedef int MazeTypeMAXLENGTHMAXLENGTH; /* 迷宫数组行列 */ /* 全局变量 */ MazeType m; /* 迷宫数组 */ int curstep=1; /* 当前足迹,初值为1 */ typedef struct /* 栈的元

8、素类型 */ int ord; /* 通道块在路径上的序号 */ PosType seat; /* 通道块在迷宫中的坐标位置 */ int di; /* 从此通道块走向下一通道块的方向(03表示东北) */ ElemType; /* 定义墙元素值为0,可通过路径为1,不能通过路径为-1,通过路径为足迹 */ Status Pass(PosType b) /* 当迷宫m的b点的序号为1(可通过路径)，return OK; 否则，return ERROR。 */ if(mb.xb.y=1) return OK; else return ERROR; void FootPrint(PosType a

9、) /* 使迷宫m的a点的序号变为足迹(curstep) */ ma.xa.y=curstep; PosType NextPos(PosType c,int di) /* 根据当前位置及移动方向，返回下一位置 */ PosType direc4=0,1,1,0,0,-1,-1,0; /* 行增量,列增量 */ /* 移动方向,依次为东南西北 */ c.x+=direcdi.x; c.y+=direcdi.y; return c; void MarkPrint(PosType b) /* 使迷宫m的b点的序号变为-1(不能通过的路径) */ mb.xb.y=-1; Status MazePath

10、(PosType start,PosType end) /* 若迷宫maze中存在从入口start到出口end的通道，则求得一条 */ /* 存放在栈中(从栈底到栈顶)，并返回TRUE；否则返回FALSE */ SqStack S; PosType curpos; ElemType e; InitStack(&S); curpos=start; do if(Pass(curpos) /* 当前位置可以通过，即是未曾走到过的通道块 */ FootPrint(curpos); /* 留下足迹 */ e.ord=curstep; e.seat.x=curpos.x; e.seat.y=curpos.

11、y; e.di=0; Push(&S,e); /* 入栈当前位置及状态 */ curstep+; /* 足迹加1 */ if(curpos.x=end.x&curpos.y=end.y) /* 到达终点(出口) */ return TRUE; curpos=NextPos(curpos,e.di); else /* 当前位置不能通过 */ if(!StackEmpty(S) Pop(&S,&e); /* 退栈到前一位置 */ curstep-; while(e.di=3&!StackEmpty(S) /* 前一位置处于最后一个方向(北) */ MarkPrint(e.seat); /* 留下不

12、能通过的标记(-1) */ Pop(&S,&e); /* 退回一步 */ curstep-; if(e.di3) /* 没到最后一个方向(北) */ e.di+; /* 换下一个方向探索 */ Push(&S,e); curstep+; curpos=NextPos(e.seat,e.di); /* 设定当前位置是该新方向上的相邻块 */ while(!StackEmpty(S); return FALSE; void Print(int x,int y) /* 输出迷宫的解 */ int i,j; for(i=0;ix;i+) for(j=0;jy;j+) printf(%3d,mij);

13、printf(n); void main() PosType begin,end; int i,j,x,y,x1,y1; printf(请输入迷宫的行数,列数(包括外墙)：); scanf(%d,%d,&x,&y); for(i=0;ix;i+) /* 定义周边值为0(同墙) */ m0i=0; /* 行周边 */ mx-1i=0; for(j=1;jy-1;j+) mj0=0; /* 列周边 */ mjy-1=0; for(i=1;ix-1;i+) for(j=1;jy-1;j+) mij=1; /* 定义通道初值为1 */ printf(请输入迷宫内墙单元数：); scanf(%d,&j)

14、; printf(请依次输入迷宫内墙每个单元的行数,列数：n); for(i=1;i=j;i+) scanf(%d,%d,&x1,&y1); mx1y1=0; /* 定义墙的值为0 */ printf(迷宫结构如下:n); Print(x,y); printf(请输入起点的行数,列数：); scanf(%d,%d,&begin.x,&begin.y); printf(请输入终点的行数,列数：); scanf(%d,%d,&end.x,&end.y); if(MazePath(begin,end) /* 求得一条通路 */ printf(此迷宫从入口到出口的一条路径如下:n); Print(x,

15、y); /* 输出此通路 */ else printf(此迷宫没有从入口到出口的路径n); 二、递归算法-用递归函数求解迷宫问题(求出所有解) #include struct PosType /* 迷宫坐标位置类型 */ int x; /* 行值 */ int y; /* 列值 */ ; #define MAXLENGTH 25 /* 设迷宫的最大行列为25 */ typedef int MazeTypeMAXLENGTHMAXLENGTH; /* 行列 */ /* 全局变量 */ struct PosType end; /* 迷宫终点位置 */ MazeType m; /* 迷宫数组 */

16、int x,y; /* 迷宫行数，列数 */ /* 定义墙元素值为0,可通过路径为-1,通过路径为足迹 */ void Print(int x,int y) /* 输出解 */ int i,j; for(i=0;ix;i+) for(j=0;jy;j+) printf(%3d,mij); printf(n); printf(n); void Try(struct PosType cur,int curstep) /* 由当前位置cur、当前步骤curstep试探下一点 */ int i; struct PosType next; /* 下一个位置 */ struct PosType direc

17、4=0,1,1,0,0,-1,-1,0; /* 行增量,列增量 */ /* 移动方向,依次为东南西北 */ for(i=0;i=3;i+) /* 依次试探东南西北四个方向 */ next.x=cur.x+direci.x; next.y=cur.y+direci.y; if(mnext.xnext.y=-1) /* 是通路 */ mnext.xnext.y=+curstep; if(next.x!=end.x|next.y!=end.y) /* 没到终点 */ Try(next,curstep); /* 试探下一点(递归调用) */ else Print(x,y); /* 输出结果 */ mn

18、ext.xnext.y=-1; /* 恢复为通路，试探下一条路 */ curstep-; void main() struct PosType begin; int i,j,x1,y1; printf(请输入迷宫的行数,列数(包括外墙)：); scanf(%d,%d,&x,&y); for(i=0;ix;i+) /* 定义周边值为0(同墙) */ m0i=0; /* 行周边 */ mx-1i=0; for(j=1;jy-1;j+) mj0=0; /* 列周边 */ mjy-1=0; for(i=1;ix-1;i+) for(j=1;jy-1;j+) mij=-1; /* 定义通道初值为-1 */ printf(请输入迷宫内墙单元数