maze.cpp

一个maze迷宫程序。内附源码注释。里面的算法便于初学者学习参考。

#include<stdio.h>
#define m 3       /* 行数*/
#define n 2       /*列数*/
#define MAXSIZE 24
struct mazetype
{
  int x,y,pre;
}  queue[MAXSIZE];
int maze[m+2][n+2];
int dx[8],dy[8];

void printpath (int recent)
{

  int i,j;
  i=recent;
  do
  {
    j=i;
    i=queue[i].pre;
    queue[j].pre=-1;
    } while (i!=0);
printf("find the path :\n\t enter->");
i=0;
while (i<MAXSIZE)
   {
     if (queue[i].pre==-1)
     printf("(%d,%d)->",queue[i].x,queue[i].y);
     i++;
    }
printf("exit\n");
}

int mazepath()
{
  int i,j,x,y,v,w=0,prior,recent,find=0,no=1;
  queue[1].x=1;                           /*从（1，1）开始搜索，将该点插入到列*/
  queue[1].y=1;
  queue[1].pre=0;
  prior=1;
  recent=1;                               /*队列指针置初值1*/
  maze[1][1]=-1;                          /*将其赋值-1，以避免回过来重复搜索*/
  printf("number xypre\n");
  printf("%4d%4d%4d%4d\n",no++,queue[recent].x,queue[recent].pre);
  while (prior<=recent && !find)          /*队列不为空且未找到路径时循环*/

  {
       x=queue[prior].x;
       y=queue[prior].y;
       /*循环扫描每个方向，把每个可走的方向插入队隐中*/

       for (v=1;v<=8;v++)
       {
          i=x+dx[v];
          j=y+dy[v];                /*选择一个前进方向（i,j)*/
          if (maze[i][y]==0)        /*如果该方向可走*/
          {
            recent++;               /*将该方向插入到队列中*/

            queue[recent].x=i;
            queue[recent].y=j;
            queue[recent].pre=prior; /*指向上一个步编号*/
            maze[i][j]=-1;           /*将其赋值以避免回过来重复搜索*/
            printf("%4d%4d%4d%4d\n",no++,  queue[recent].x,
                   queue[recent].y,queue[recent].pre);
                                                  }
    if (i==m && j==n)                 /*找到出口*/
      {
       printpath(recent);             /*打印找到路径*/
       find=1;                        /*设置为1时便于退循环*/
       }
       w++;
    }
    prior++;                          /*从队列中删除一个元素*/
  }
  if (!find)printf("there is no path!\n");
  return w;
}



void main()
{
  int i,j,h;
  for (i=1;i<=m;i++)                    /*获取迷宫数据*/
     for (j=1;j<=n;j++)
        scanf("%1d",&maze[i][j]);
  for (i=0;i<m+1;i++)                   /*加上为1的外框*/
  {
     maze[i][0]=1;maze[i][n+1]=1;
   }
   for (j=0;j<=n+1;j++)
   {
      maze[0][j]=1;
      maze[m+1][j]=1;
    }
    dx[1]=-1;dx[2]=-1;dx[2]=0;dx[4]=1;      /*建立方向数据*/
    dx[5]=1;dx[6]=1;dx[7]=0;dx[8]=-1;
    dy[1]=0;dy[2]=1;dy[3]=1;dy[4]=1;
    dy[5]=0;dy[6]=-1;dy[7]=-1;dy[8]=-1;
  h=mazepath();                             /*产生迷宫路径*/
  printf("\n\n\n\n%d\n\n",h);               /*打印时间复杂度*/
}