迷宫求解-栈的应用（穷举法）

addictlinux

我的问题，请看附录。
程序如下：

#include<stdio.h> #include<stdlib.h> #define TRUE 0 #define FALSE 1 #define MAXLEN 10 #define STACK_INIT_SIZE 1000 #define STACK_INC_SIZE 500 typedef int Status; typedef struct{ &nbsp;&nbsp;&nbsp;int r; &nbsp;&nbsp;&nbsp;int c; }PositionType; typedef struct{ &nbsp;&nbsp;&nbsp;int order; &nbsp;&nbsp;&nbspositionType seat; &nbsp;&nbsp;&nbsp;int dir; }SElemType; typedef struct{ &nbsp;&nbsp;SElemType *base; &nbsp;&nbsp;SElemType *top; &nbsp;&nbsp;int StackSize; }SqStack; typedef struct{ &nbsp;&nbsp;int r; &nbsp;&nbsp;int c; &nbsp;&nbsp;char adr[MAXLEN][MAXLEN]; }MazeType; Status InitStack(SqStack *s) { &nbsp;&nbsp;s->base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); &nbsp;&nbsp;if(s->base!=NULL){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;s->top=s->base; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;s->StackSize=STACK_INIT_SIZE; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;return TRUE; } void Push(SqStack *s,SElemType *e) { &nbsp;&nbsp;SElemType *tmpP; &nbsp;&nbsp;if(s->top-s->base>=s->StackSize) &nbsp;&nbsp;&nbsp;tmpP=(SElemType *)realloc(s->base,(STACK_INIT_SIZE+STACK_INC_SIZE)*sizeof(SElemType)); &nbsp;&nbsp;&nbsp;if(tmpP!=NULL){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;s->base=tmpP; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;s->top=s->base+s->StackSize; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;s->StackSize+=STACK_INC_SIZE; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;*(s->top++)=*e; } void Pop(SqStack *s,SElemType *e) { &nbsp;if(s->top>s->base) &nbsp;&nbsp;&nbsp;*e=*(--s->top); } &nbsp;&nbsp;&nbsp; Status StackEmpty(SqStack *s) { &nbsp;&nbsp;if(s->top==s->base) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return TRUE; &nbsp;&nbsp;&nbsp;else &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return FALSE; } Status DestoryStack(SqStack *s) { &nbsp;&nbsp;s->base=s->top; &nbsp;&nbsp;free(s->base); &nbsp;&nbsp;if(s->base==NULL) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return TRUE; &nbsp;&nbsp;else &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return FALSE; } Status Pass(MazeType maze,PositionType curpos,SqStack *s) { &nbsp;&nbsp;SElemType *p; &nbsp;&nbsp;p=s->top; &nbsp;&nbsp;if(StackEmpty(s)==TRUE) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(maze.adr[curpos.r][curpos.c]=='0') &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return TRUE; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return FALSE; &nbsp;&nbsp;else{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(maze.adr[curpos.r][curpos.c]=='0') &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while((--p)->seat.r!=maze.r && p->seat.c!=maze.c)//判断坐标是否在路径中存在。 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(p==s->base) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return TRUE; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return FALSE; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp; } void FootPrint(MazeType maze,PositionType curpos) { &nbsp;&nbsp;&nbsp;maze.adr[curpos.r][curpos.c]='*'; } PositionType NextPos(PositionType curpos,int i) { &nbsp;&nbspositionType cpos; &nbsp;&nbsp;cpos=curpos; &nbsp;&nbsp;switch(i){ &nbsp;&nbsp;&nbsp;&nbsp;case 1:cpos.c+=1;break; &nbsp;&nbsp;&nbsp;&nbsp;case 2:cpos.r+=1;break; &nbsp;&nbsp;&nbsp;&nbsp;case 3:cpos.c-=1;break; &nbsp;&nbsp;&nbsp;&nbsp;case 4:cpos.r-=1;break; &nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;return cpos; } void  MarkPrint(MazeType maze,PositionType curpos) { &nbsp;&nbsp;maze.adr[curpos.r][curpos.c]='#'; } void PrintMaze(MazeType maze){ &nbsp;int i,j; &nbsp;&nbsp;for(i=0;i<=9;i++) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf("\n"); &nbsp;&nbsp;&nbsp;&nbsp;for(j=0;j<=9;j++) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf("%3c",maze.adr[i][j]); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf("\n"); }

addictlinux

Status MazePath(MazeType maze,PositionType start,PositionType end) { &nbsp;&nbsp;SqStack s; &nbsp;&nbspositionType curpos; &nbsp;&nbsp;int curstep; // 1->east, 2->south,3->west,4->north &nbsp;&nbsp;SElemType *e; &nbsp;&nbsp;curpos=start; &nbsp;&nbsp;curstep=1; if(InitStack(&s)==TRUE){ &nbsp;&nbsp;do{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(Pass(maze,curpos,&s)==TRUE){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;FootPrint(maze,curpos); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;e->order=curstep; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;e->seat=curpos; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;e->dir=1; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbspush(&s,e); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(curpos.r==end.r && curpos.c==end.c){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(DestoryStack(&s)==TRUE) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return TRUE; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;exit(0); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;curpos=NextPos(curpos,1); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;curstep++; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(StackEmpty(&s)!=TRUE) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbspop(&s,e); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while(e->dir==4 && StackEmpty(&s)!=TRUE){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;MarkPrint(maze,e->seat); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbspop(&s,e); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(e->dir<4){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;e->dir++; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbspush(&s,e); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;curpos=NextPos(e->seat,e->dir); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;}while(StackEmpty(&s)!=TRUE);       &nbsp;} }             main() { &nbsp;&nbsp;MazeType maze; &nbsp;&nbspositionType start,end; &nbsp;&nbsp;start.r=1; &nbsp;&nbsp;start.c=1; &nbsp;&nbsp;end.r=8; &nbsp;&nbsp;end.c=8; &nbsp;&nbsp;char a[][MAXLEN]={ &nbsp;&nbsp;&nbsp;&nbsp;{'1','1','1','1','1','1','1','1','1','1'}, &nbsp;&nbsp;&nbsp;&nbsp;{'1','0','0','0','0','1','1','1','1','1'}, &nbsp;&nbsp;&nbsp;&nbsp;{'1','1','0','0','1','1','1','1','1','1'}, &nbsp;&nbsp;&nbsp;&nbsp;{'1','0','1','0','0','0','1','1','1','1'}, &nbsp;&nbsp;&nbsp;&nbsp;{'1','0','1','0','1','0','1','1','1','1'}, &nbsp;&nbsp;&nbsp;&nbsp;{'1','0','1','0','0','0','1','1','1','1'}, &nbsp;&nbsp;&nbsp;&nbsp;{'1','1','1','1','1','0','0','0','1','1'}, &nbsp;&nbsp;&nbsp;&nbsp;{'1','1','1','1','1','1','1','0','0','1'}, &nbsp;&nbsp;&nbsp;&nbsp;{'1','1','1','1','1','1','1','1','0','1'}, &nbsp;&nbsp;&nbsp;&nbsp;{'1','0','1','1','1','1','1','1','1','1'} &nbsp;&nbsp;&nbsp;&nbsp;}; &nbsp;&nbsp;char *p1,*p2; &nbsp;&nbsp;int i,j; &nbsp;&nbsp;p1=(char *)maze.adr; &nbsp;&nbsp;p2=(char *)a; &nbsp;&nbsp;for(i=0;i<(sizeof(a)/sizeof(char));i++) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*p1++=*p2++; &nbsp;&nbsp; &nbsp;if(MazePath(maze,start,end)!=TRUE) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf("No path from entrance to exit \n"); &nbsp;else &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsprintMaze(maze); }

南无小和尚

顶，学习了，学数据结构时候经常讲迷宫

Just竹本

{:3_200:}