www.pudn.com > MAZE_wdone.rar > MAZE_wdone.C

#include 
#include 
#include 
#define M 100 
#define N 100 
#define K 8       /*迷宫二维数组的行列大小*/ 
#define MAXLEN M*N 
int q; 
 
typedef struct    /*结构体中x,y是坐标的行，列,d是记录方向的值*/ 
{ 
 int x; 
 int y; 
 int d; 
}Node;      
 Node tempnode[M]; 
 Node temp_node[M][N]; 
typedef struct ST     /*定义栈的数据结构*/ 
{ 
 int top; 
 Node data[MAXLEN]; 
}stack,*st; 
st t;  
 
/*建空栈*/ 
st create_emptystack() 
{ 
 st t; 
 t=(st)malloc(sizeof(stack)); 
 if(t==NULL) 
  printf("Out of space!\n"); 
 else 
  t->top=-1; 
 return t; 
} 
 
/*判断是否为空栈,空就置一*/ 
int if_empty_stack(st t) 
{ 
 if(t->top==-1) return 1; 
 else return 0; 
}  
 
/*将元素n进栈*/ 
push_stack(st t,Node n) 
{ 
 if(t->top==MAXLEN-1)  
     printf("Stack is full.\n"); 
 else 
 { 
  t->top++; 
  t->data[t->top]=n; 
 } 
} 
 
/*栈顶元素出栈,指针指向下一元素*/ 
pop_stack(st t) 
{ 
 if(t->top==-1) 
  printf("Stack is empty.\n"); 
 else 
  t->top--; 
} 
 
/*将当前的所有状态量压入栈顶*/ 
void pushtostack(st t,int x,int y,int d) 
{ 
 Node temp; 
 temp.x=x; temp.y=y; temp.d=d; 
 push_stack(t,temp); 
} 
 
/*获得栈顶元素*/ 
Node get_top(st t) 
{ 
 return (t->data[t->top]); 
} 
 
/*保存所有可行路径*/ 
void save_road(st t) 
{ 
 int flag; 
 flag=t->top; 
 q=0; 
 t->top=0; 
 while(!if_empty_stack(t)) 
 {  
  tempnode[q]=get_top(t);   /*将路径保存到一个tempnode中*/ 
  q++;   
  if(t->top>=flag) break; 
  t->top++; 
  } 
} 
 
/*走迷宫路径*/ 
void MG_path(int mg[][K],int increase[4][2],int a,int b)  /*increase是一个已存有方向增量的数组*/ 
{ /*a,b是终点的行，列值*/ 
 st S; 
 Node tempvalue; 
 int xn,yn,i,x,y; 
 S=create_emptystack(); 
 mg[1][1]=2;            /*将起点标记为2*/ 
 pushtostack(S,1,1,0);  /*将它入栈*/ 
 
 while(!if_empty_stack(S))  /*这是用来记录可行路径的一个循环体*/ 
 { 
  tempvalue=get_top(S);    
  pop_stack(S); 
   x=tempvalue.x; 
   y=tempvalue.y; 
 
  for(i=0;i<4;i++)    /*4个方向分别作判断的循环体*/ 
  { 
   xn=x+increase[i][0]; 
   yn=y+increase[i][1]; 
   if(mg[xn][yn]==0)   /*判断此方向上的下一个坐标是否可走*/ 
   { 
    mg[xn][yn]=2;   /*先将下一个坐标变成2，以便和标记墙的1区分*/ 
    pushtostack(S,x,y,i);   /*间当前的坐标值入栈*/ 
    x=xn;y=yn;i=-1;    /*将这下一个坐标值变成下次循环的当前值*/ 
    if(xn==a&&yn==b)   /*判断是否到了终点*/ 
    { 
     pushtostack(S,xn,yn,i);    
     save_road(S);   /*保存将所有路径*/ 
     return; 
    } 
   } 
  } 
 } 
 printf("Sorry!!Fail to pass.\n"); 
} 
 
main() 
{ 
 int mgn[K][K]; 
 int increase[][2]={0,1,1,0,0,-1,-1,0};        /*定义increase的方向变量*/ 
 int incre_pre[M][2]; 
 int a=0,b=0,c,r=0,i,j,s,t=0,v,k=-1; 
 int m=0,flag=0,p,length[M],jl[M]; 
 int mg[][K]={              
        1,1,1,1,1,1,1,1, 
        0,0,1,0,1,0,0,1, 
        1,0,0,0,0,0,1,1, 
        1,0,1,0,1,0,1,1,              /*初始化迷宫数组*/ 
        1,0,0,0,0,0,0,1, 
        1,0,1,0,1,1,0,1, 
        1,0,0,0,0,0,0,0, 
        1,1,1,1,1,1,1,1 
        }; 
 
 while(t<=3)          
 { 
  for(s=t;s<=t+3;s++)        /*此循环是为了让系统每次读取increase的值都不同*/ 
  { 
    if(k<3)           /*如果循环到了increase最后的那个值时，k就标记为0*/ 
    k++; 
    else  k=0; 
    for(v=0;v<2;v++)         /*将每次不同的increase值存到新数组incre_pre里*/ 
     incre_pre[k][v]=increase[s%4][v];      
  } 
   for(i=0;i0)      /*不同路径有不同长度*/ 
    { 
     if(p<10)             
      printf("0%d---%d,%d",p,temp_node[t][p-1].x,temp_node[t][p-1].y);    /*分0-9和9以上两种不同格式的输出*/ 
     else 
      printf("%d---%d,%d",p,temp_node[t][p-1].x,temp_node[t][p-1].y); 
     if(p%4==0)            /*下面是为了输出格式的好看*/ 
      printf("\n"); 
     else 
      printf("\t\t"); 
     p++; 
     length[t]--; 
    } printf("\n"); 
 
   } 
   getch(); 
   printf("\n"); 
   t++; 
  } 
  getch(); 
 return 0; 
}