迷宫.txt

讲述迷宫算法的思想与代码生成方法

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define M 10
#define N 10
typedef struct node
{
int row; /*记录行*/
int col; /*记录列*/
struct node *next;
}stack;
stack *top;   //链指针,指向栈顶

int pd_Migong(char a[M][N]) //函数,判断迷宫模型是否满足要求
{
int i,j,temp=0;
for(j=0;j<N;j++)         
{
    if((a[0][j]!='#')||(a[M-1][j]!='#'))   //判断第0行和第M-1行是否为"#"
{
   temp=1;
   break;
}
}
if(temp==0)
{
   for(i=0;i<M;i++)
   {
    if((a[i][0]!='#')||(a[i][N-1]!='#')) //判断第0列和第N-1列是否为"#"
{
   temp=1;
   break;
}
}
}
return temp;
}

void entermg(char a[M][N])    /*输入迷宫模型*/  
{
int i,j,t=0;
char ch; 
printf("\n请输入(%d*%d)迷宫模型,以(#)表示不通,以(0)表示通路,模型四周为(#),(%d,%d)表示出口:\n",M,N,M-1,N-1);
       for(i=0;i<M;i++)
   { for(j=0;j<N;j++)
        scanf("%c",&a[i][j]);
        scanf("%c",&ch);
   }
t=pd_Migong(a);                   //调用pd_Migong
while(a[M-2][N-2]=='#'||t)
       {
    printf("你输入的迷宫模型错误!\n");
           printf("请重新输入(%d*%d)迷宫模型,以(#)表示不通,以(0)表示通路,模型四周为(#),(%d,%d)表示出口:\n",M,N,M-1,N-1);
            for(i=0;i<M;i++)
        { for(j=0;j<N;j++)
             scanf("%c",&a[i][j]);
             scanf("%c",&ch);
         }
         t=pd_Migong(a);
       }

}


void print(char a[M][N])        /*打印迷宫*/
{
int i,j;
int x;
printf(" ");
for(x=0;x<N;++x)       //打印列标记 
      printf("%4d",x);
      printf("\n");
for(i=0;i<M;i++)
     {   printf("%d",i);    //行标记
   for(j=0;j<N;j++)
      printf("%4c",a[i][j]);           
             printf("\n");
     }
}

stack * initateles(stack *s)/*初始化栈，即定义栈顶*/
{
s=(stack*)malloc(sizeof(stack));
s->next=NULL;
return s;
}

stack * push_stack(stack *s,int row,int col) /*通路标记进栈*/
{
   stack * New;
   New=(stack*)malloc(sizeof(stack));
   New->row=row;
   New->col=col;
   New->next=s;   //指向旧栈顶
   s=New;         //S指向新栈顶
   return s; 
}

stack * pop_stack(stack * s) /*四方不通则出栈*/
{
    stack *p;
    p=s;
    s=p->next; //栈顶向下移
    free(p); 
    return s; 
}

void print_stack(stack *s) /*遍历栈及打印路径*/
    {
       stack *sl; 
       typedef struct path   //新建栈存储路径,以便正确输出路径
   {
     int row;        /*记录行*/
     int col;        /*记录列*/
     struct path *next;
          }list;
       list *p,*pa;
       p=(list*)malloc(sizeof(list));   //初始化新栈
       p->next=NULL;
   while(s->next!=NULL)                //遍历旧栈,输出原始数据
     {      
        sl=s;
        s=sl->next;                       //栈顶向下移
pa=(list*)malloc(sizeof(list));   //保存到新栈
        pa->row=sl->row;
        pa->col=sl->col;
free(sl);                          //释放旧栈空间
        pa->next=p;
        p=pa;                           //新栈顶指针上移,指向当前栈顶
     }
   printf("入口:");
   while(p->next!=NULL)    //遍历新栈并输出路径
     {
         pa=p;
p=pa->next;
         printf("(%d,%d) -> ",pa->row,pa->col);
free(pa);
     }
   printf("出口\n");
}

stack *path(stack *top,char Migong[M][N],int i,int j)//判断是否为通路
    { 
stack *tp;
         top=push_stack(top,i,j);    //入口坐标进栈
         do
             {
          if((Migong[i+1][j]!='#')&&(Migong[i+1][j]!='1'))   /*判断南邻是否为通路,通则进栈*/
                 {
                     i=i+1;
                     top=push_stack(top,i,j);
                     Migong[i][j]='1'; 
   
                     }                 
                 else     if((Migong[i][j+1]!='#')&&(Migong[i][j+1]!='1')) /*判断东邻是否为通路,通则进栈*/
                            {
                               j=j+1;
                               top=push_stack(top,i,j);            /*通则进栈*/
                               Migong[i][j]='1';                  /*做标记*/
                            }
                     else if((Migong[i-1][j]!='#')&&(Migong[i-1][j]!='1')) /*判断北邻是否为通路,通则进栈*/
                               {
                               i=i-1;
                                  top=push_stack(top,i,j);
                                  Migong[i][j]='1';
                               }
                            else if((Migong[i][j-1]!='#')&&(Migong[i][j-1]!='1')) /*判断西邻是否为通路,通则进栈*/
                                      {
                                     j=j-1;
                                        top=push_stack(top,i,j);
                                        Migong[i][j]='1';
                                      }                    

                                    else top=pop_stack(top);             /* 若都不通则退栈 */ 
          tp=top;
          if(top->next==NULL)    
                       break;
   else
      {
                   i=tp->row;   //读取当前栈顶元素数据
                j=tp->col;
      }
     }while(!(i==(M-2)&&j==(N-2))); /*判断出口*/
   return top;
}


void main()
{
    char Migong[M][N];
    int i,j; 
    entermg(Migong);            /*输入迷宫模型*/      
    printf("迷宫模型:\n");       
    print(Migong);               /*打印迷宫*/ 
    top=initateles(top);
    printf("\n请输入入口位置：\n");
    printf("row= ");
scanf("%d",&i);
printf("col= ");
scanf("%d",&j);
    while((i>M-1)||(j>N-1)||Migong[i][j]=='#')    //入口坐标不能越界也不能为是"#"标记
{
        printf("你输入的迷宫入口(%d,%d)错误!必须以(0)标记为入口!\n",i,j);
   printf("请重新输入迷宫入口坐标:\n");
   printf("row= ");
   scanf("%d",&i);
   printf("col= ");
   scanf("%d",&j);
}
top=path(top,Migong,i,j);
if(top->next==NULL)         //判断是否为通路
{
   printf("没有通路!\n");
}
else
{
    printf("\n成功路径为:");
    print_stack(top); //输出路径
    printf("\n");
}
}