mazepath1.txt

迷宫程序1

#define TRUE                 1
#define FALSE                0
#define OK                   1
#define ERROR               0
#define INFEASIBLE          -1
#define OVERFLOW          -2
#define NULL                0
#define MAXLEN           100
#define STACK_INCREASE    10
typedef int Status;
typedef  struct{
int  i;
 int  j;
}PosType;
typedef struct{
int       ord;
 PosType   seat;
 int       di;
}ElemType;
typedef struct{
ElemType   *base;
 ElemType   *top;
 int         maxsize;
}SqStack;
typedef struct{
int data;
}Maze[10][10];

Status InitStack(SqStack *S) {
 S->base=(ElemType *)malloc(100 * sizeof(ElemType));
 if (!S->base) exit(OVERFLOW);
 S->top=S->base;
 S->maxsize=MAXLEN;
 return OK;
}
Status GetTop(SqStack S,ElemType *e) {
if (S.top==S.base)
 return  ERROR;
 *e=*(S.top-1);
 return OK;
}
Status Push(SqStack *S,ElemType e) {
if ((S->top-S->base)>=S->maxsize) {
	   S->base=(ElemType *) realloc(S->base,(S->maxsize+10)*sizeof(ElemType));
	   if(!S->base) exit(OVERFLOW);
	   S->top=S->base+S->maxsize;
	   S->maxsize+=STACK_INCREASE;
 }
 *S->top++=e;
 return OK;
}

Status Pop(SqStack *S,ElemType *e) {
if (S->top==S->base) return ERROR;
 *e=*--S->top;
}
Status StackEmpty(SqStack S) {
if (S.top==S.base) return OK;
 else return FALSE;
}

Status Pass(PosType pos,Maze maze) {
if (maze[pos.i][pos.j].data==0) return OK;
 else return ERROR;
}
void FootPrint(PosType a,Maze maze)
{maze[a.i][a.j].data=1;}
void NextPos(PosType *pos,int di) {
switch(di) {
  case 1: pos->j+=1;break;
  case 2: pos->i+=1;break;
  case 3: pos->j-=1;break;
  case 4: pos->i-=1;break;
 }
}
void MarkPrint(PosType a,Maze maze)
{maze[a.i][a.j].data=-1;}

Status MazePath(Maze maze,PosType start) {
SqStack S;int curstep;PosType curpos;ElemType e;
 InitStack(&S);
 curpos=start;
 curstep=1;
 do{if(Pass(curpos,maze)){FootPrint(curpos,maze);
			  e.ord=curstep;e.seat=curpos;e.di=1;
			  Push(&S,e);
			  if (curpos.i==9&&curpos.j==8)  return(TRUE);
			  NextPos(&curpos,1);
			  curstep++;
	 }
     else{if(!StackEmpty(S)){Pop(&S,&e);
			   while(e.di==4&&!StackEmpty(S))
				 {MarkPrint(e.seat,maze);Pop(&S,&e);}
			   if(e.di<4){e.di++;Push(&S,e);
			            NextPos(&e.seat,e.di);
			            curpos=e.seat;
           }
          }
      }
 }while(!StackEmpty(S));
 return (FALSE);
}

void show(Maze maze) {
int m,n;
for(m=0;m<=9;m++){
    printf("\n");
for(n=0;n<=9;n++) {
if (maze[m][n].data==0||maze[m][n].data==-1) printf(" ");
	   if (maze[m][n].data==1) printf("*");
	   if (maze[m][n].data==2) printf("N");
	   if (maze[m][n].data==3) printf("i");
	 }
  }
}

main(){
Maze maze0,maze1;int m,n,data;PosType a;
 for(m=1;m<=8;m++)
   for(n=1;n<=8;n++){maze0[m][n].data=0;maze1[m][n].data=0;}
 for(m=0,n=0;n<=9;n++){maze0[m][n].data=2;maze1[m][n].data=2;}
 for(m=9,n=0;n<=9;n++){maze0[m][n].data=2;maze1[m][n].data=2;}
 for(m=1,n=0;m<=9;m++){maze0[m][n].data=2;maze1[m][n].data=2;}
 for(m=1,n=9;m<=9;m++){maze0[m][n].data=2;maze1[m][n].data=2;}
 maze0[0][1].data=0;maze0[9][8].data=0;maze1[0][1].data=0;maze1[9][8].data=0;
 show(maze0);
 for(m=1;m<=8;m++)    /*mase0[ ][ ]引导用户输入迷宫*/
   for(n=1;n<=8;n++){loop:  maze0[m][n].data=3;show(maze0);
		     printf("\n\nPlease input a Maze:(pass:0 wall:2)\n");
		     scanf("%d",&data);
		     if (data==0||data==2)
		       {maze0[m][n].data=data;maze1[m][n].data=data;}
		     else goto loop;
		     show(maze0);
		    }
 a.i=0;a.j=1;
 MazePath(maze1,a);
 printf("\n*********************The Result******************\n\n");
 show(maze1);
 printf("\nPress any to Exit.....");
 getch();
}