5.txt

迷宫 数据结构与算法中的重要例题 很有代表性

#include <stdio.h>
#define m 8
#define n 8
#define MAXSIZE 100


 typedef struct    /*方向数组*/
{int i,j;}item;

typedef struct{

 item p;
 int di;
} datatype;

 typedef struct 
{
  int top;
  datatype data[MAXSIZE];

  }SeqStack;


 SeqStack *Init_SeqStack(SeqStack *s)        /*置空栈*/
{  s=(SeqStack *)malloc(sizeof(SeqStack));
  s->top=-1;
  return s; /* top指向栈顶的上一个元素 */
}



int Push_SeqStack(SeqStack *s,datatype x)    /* 把元素x压入栈 */
  {
    if(s->top==MAXSIZE-1)    return 0;        /* 判断栈是否为满栈 */

    else
       {
         
         s->data[s->top]=x;
         s->top++;
         return 1;
         }
}

int Pop(SeqStack *s, datatype *x)    /*出栈*/
 {
   if(s->top==0) return 0;   /* 判断栈是否为空 */

   else
    { s->top--;
     *x=s->data[s->top];
     
     return 1;}
 }


 int Top_SeqStack(SeqStack *s,datatype *x)  /* 取栈顶元素的值 */
{
  if(s->top==0)  return 0;/*栈空*/

  else
   {
  s->top--;
  *x= s->data[s->top];
  return 1;  }

}


 main()
{
  SeqStack S;
  datatype e;
  item p,p_end;
  int maze[m+2][n+2]={      /* 离散迷宫矩阵，1表示墙壁 */
   {1,1,1,1,1,1,1,1,1,1,},
   {1,0,1,0,0,0,0,0,0,1,},
   {1,0,1,0,1,1,1,1,0,1,},
   {1,0,0,0,1,0,0,0,0,1,},
   {1,0,1,1,1,0,1,0,0,1,},
   {1,0,1,0,1,0,0,1,0,1,},
   {1,1,1,1,1,0,0,1,0,1,},
   {1,0,0,1,0,1,0,0,1,1,},
   {1,1,1,0,0,0,1,0,0,1,},
   {1,1,1,1,1,1,1,1,1,1,},
  };
  int i,j;

  Init_SeqStack(&S);
  p_end.i=8;p_end.j=8;
  p.i=1;p.j=1;

  do {
    if (maze[p.i][p.j]==0) {  /* 当前位置不是墙壁并且没走过 */
      maze[p.i][p.j]=-1;   /* 标记已走过 */
      e.p = p;
      e.di = 1;
      Push_SeqStack(&S,e);           /* 加入路径 */
      if (p.i==p_end.i && p.j==p_end.j)     /* 如果已经到达终点，退出循环，求得的路径放在栈中 */
        break;
      else
        p.j++;            /* 下一个位置是当前位置的右邻 */
    }
    else{  /* 当前位置不能通过 */
      if(S.top>0){
        Pop(&S,&e);
        while(e.di==4 && S.top>0){
          maze[e.p.i][e.p.j]=2;  /* 留下不能通过的标记，并退回一步 */
          Pop(&S,&e);
        }
        if (e.di<4){
          e.di++; Push_SeqStack(&S,e);      /* 换下一个方向搜索 */
          p.i=e.p.i; p.j=e.p.j;
          if (e.di==2) p.i++;    /* 设定当前位置是该方向上的相邻块“右下左上” */
          else if (e.di==3) p.j--;
          else if (e.di==4) p.i--;
        }
      }
    }
  }while(S.top>0);


  /* 求得的路径放在栈中 */
  printf("\n");
  while(Pop(&S,&e))
    printf("\n(%d,%d)",e.p.i,e.p.j);


  /* 打印出整个迷宫，2的是所找到的路径，-1是走过的不通的路径 */
  printf("\n\n");
  for(i=0;i<m+2;i++) {
    for(j=0;j<n+2;j++)
      printf("%2d ",maze[i][j]);
    printf("\n");
  }

  getch();
}