file27.c

来自「用C语言来实现的10维迷宫问题 来字符的作品 来自一个很用C语言来实现的10维迷」· C语言 代码 · 共 197 行

#include<stdio.h>
#define stack_init_size 10
#define stackincrement 1
#define M2 10
#define N2 10
int M=M2-2,N=N2-2;
typedef int Mazetype;
typedef struct{
int x;
int y;
}Postype;
typedef struct{
int ord;
Postype seat;
int di;
}SElemtype;
typedef struct{
SElemtype *base;
SElemtype *top;
int stacksize;
}SqStack;
struct moved {
int dx,dy;
};
SqStack S;
void main()
{void initmaze(Mazetype maze[][N2]);
 void initmoved(struct moved move[]);
 int MazePath(Mazetype maze[][N2],struct moved move[],Postype,Postype);
 Mazetype maze[M2][N2];
 struct moved move[5];
 Postype start,end;
 start.x=1;
 start.y=1;
 end.x=8;
 end.y=8;
 initmaze(maze);
 initmoved(move);
 MazePath(maze,move,start,end);
 getch();
}
void initmaze(Mazetype maze[][N2])
{int i,j,num;
 for(i=1;i<=M;i++)
  { for(j=1;j<=N;j++)
    {num=(i+j*3-1)%3;
     if(num==1)
     maze[i][j]=1;
     else maze[i][j]=0;
	}
	}
  for(i=0,j=0;i<=M+1;i++)
   maze[i][j]=1;
   for(i=0,j=0;j<=N+1;j++)
   maze[i][j]=1;
   for(i=M+1,j=0;j<=N+1;j++)
   maze[i][j]=1;
   for(j=N+1,i=0;i<=M+1;i++)
   maze[i][j]=1;
   for(i=0;i<=M+1;i++)
    {for(j=0;j<=N+1;j++)
     printf("%3d",maze[i][j]);
     printf("\n");
     }
     printf("----------------------------------------\n");
   }

void initmoved(struct moved move[])
{move[1].dx=1;
 move[1].dy=0;
 move[2].dx=0;
 move[2].dy=1;
 move[3].dx=-1;
 move[3].dy=0;
 move[4].dx=0;
 move[4].dy=-1;
}
int MazePath(Mazetype maze[][N2],struct moved move[],Postype start,Postype end)
{int InitStack();
 Mazetype Pass(Postype,Mazetype maze[][N2]);
 void Footprint(Postype,Mazetype maze[][N2]);
 Postype Nextpos(Postype,struct moved move[],int);
 int Push(SElemtype);
 int StackEmpty();
 SElemtype Pop();
 void Markprint( Mazetype maze[][N2], Postype );
 Postype curpos;
 SElemtype e;
 int curstep,i,j;
 InitStack();
 curpos=start;
 curstep=1;
 do{
    if(Pass(curpos,maze)){
     Footprint(curpos,maze);
     e.ord=curstep;
     e.seat=curpos;
     e.di=1;
     Push(e);
     if(curpos.x==end.x&&curpos.y==end.y)
     return(1);
     curpos=Nextpos(curpos,move,1);
     curstep++;
     }
     else{
     if(!StackEmpty())
     {Pop(e);
      while(e.di==4&&!StackEmpty()){
      Markprint(maze,e.seat);
      Pop(e);
      }
      if(e.di<4){
      e.di++;
      Push(e);
      curpos=Nextpos(e.seat,move,e.di);
      }
      }
      }
      }while(!StackEmpty());
      for(i=0;i<=M+1;i++)
	{for(j=0;j<=N+1;j++)
	 printf("%3d",maze[i][j]);
	 printf("\n");
	 }
      return(0);
      }
   int InitStack()
   {S.base=(SElemtype *)malloc(stack_init_size*sizeof(SElemtype));
    if(!S.base)
    return(0);
    S.top=S.base;
    S.stacksize=stack_init_size;
    return(1);
    }
   Mazetype Pass(Postype curpos,Mazetype maze[][N2])
   {int i,j;
    i=curpos.x;
    j=curpos.y;
    if(maze[i][j]==0)
    return(1);
    else return(0);
   }
   void Footprint(Postype curpos,Mazetype maze[][N2])
   {int i,j;
    i=curpos.x;
    j=curpos.y;
    maze[i][j]=-1;
   }
   int Push(SElemtype e)
   {if(S.top-S.base>=S.stacksize)
    {S.base=(SElemtype *)realloc(S.base,(S.stacksize+stackincrement)*sizeof(SElemtype));
     if(!S.base)
     return(0);
     S.top=S.base+S.stacksize;
     S.stacksize+=stackincrement;
     }
     *S.top++=e;
     return(1);
     }
    Postype Nextpos(Postype curpos,struct moved move[],int  di)
    {SElemtype e;
     int i,j;
     i=curpos.x+move[di].dx;
     j=curpos.y+move[di].dy;
     e.seat.x=i;
     e.seat.y=j;
     return(e.seat);
    }
    int StackEmpty()
    {if(S.base==NULL||S.base!=S.top)
     return(0);
     return(1);
    }
    SElemtype Pop()
    {SElemtype e;
     if(S.base==NULL||S.base==S.top)
     {e.ord=0;
      e.seat.x=0;
      e.seat.y=0;
      e.di=0;
      return(e);}
    { e=*--S.top;
      return(e); }
    }
    void Markprint(Mazetype maze[][N2],Postype foot)
    {int i,j;
     i=foot.x;
     j=foot.y;
     maze[i][j]=8;
    }