迷宫程序3.txt

我的C语言作业

#include"time.h"
#include "stdio.h"
#include "graphics.h"
#include "conio.h"
#include "stdlib.h"
#define MaxX 50   /*迷宫的最大行数*/
#define MaxY 50   /*迷宫的最大列数*/
typedef struct node
{
  int x;
  int y;
}queue;   /*定义队列，用于存放迷宫的路径*/
typedef struct
{
  queue data[255];
  int rear,front;
}Queue;
typedef Queue *Node;
Node result;
int X,Y;  /*迷宫的大小*/
int Map[MaxX][MaxY];  /*迷宫结构*/

void init_queue() /*队列初始化*/
{
  int i;
  result=(Node)malloc(sizeof(Queue));
  for(i=0;i<255;i++)
    result->data[i].x=result->data[i].y=0;
  result->front=result->rear=0;
}
void en_queue(int x,int y)  /*入队*/
{
  result->data[result->rear].x=x;
  result->data[result->rear].y=y;
  result->rear++;
}
queue del()  /*删除刚入队元素*/
{
  queue p;
  result->rear--;
  p=result->data[result->rear];
  return p;
}
int empty_queue()  /*判断队列是否为空*/
{
  return(result->front==result->rear);
}
void Setmap()         /*手工输入迷宫函数*/
{
  int i,j,t;
  printf("\n依次输入迷宫的结构(1为墙，0为通路):\n");
  for(i=0;i<=X+1;i++)
    {
      for(j=0;j<=Y+1;j++)
{
   if(i==0 || j==0 || i==X+1 || j==Y+1)    /*在迷宫周围包上一圈1，防止搜索通路时越界*/
     {
       Map[i][j]=1;
       continue;
     }
   else
     {
       scanf("%d",&t);             /*手工输入迷宫的墙与通路*/
       Map[i][j] = (t!=0) ? 1 : 0;
     }
}
   }
}
void AutoSetMap()         /*电脑绘制迷宫*/
{
  int a=20,b=10,i,j;      /*a、b用于产生不同的随机数种子*/
  for(i=0;i<=X+1;i++)
    {
      for(j=0;j<=Y+1;j++)
        {
          if(i==0 || j==0 || i==X+1|| j==Y+1)
            {
              Map[i][j]=1;
              continue;
            }
   srand((rand()*(a++)+(b++))%65536); /*srand和rand函数配合使用，产生随机数的起始发生数据*/
   Map[i][j]=rand()%2;     /*产生的随机数mod2所得的余数为1或者0，作为迷宫的墙或通路*/
        }
    }
}
void mouse(int x,int y)  /*画出当前位置*/
{
int x1,y1;
x1=105+30*(y-1);
y1=65+30*(x-1);
line(x1-10,y1,x1+10,y1);    /*在通路的地方画线*/
line(x1,y1-10,x1,y1+10);
}
void erasermouse(int x,int y)    /*擦除所走过的点*/
{
int x1,y1;
x1=105+30*(y-1);
y1=65+30*(x-1);
setcolor(15);  /*15表示白色*/
line(x1-10,y1,x1+10,y1);   /*将刚刚画过线的地方用白色再画一次，也就将刚才画的线覆盖掉*/
line(x1,y1-10,x1,y1+10);
setcolor(4);  /*红色，再将当前颜色变成红色*/
}
void TIMEDELAY()      /*时间延迟函数，这样动态实现时才可以看清 */
{
  double i;
  for(i=0;i<9e+6;i++);   /*执行一个空循环，达到延时的效果*/
}
void SearchWay()            /*查找最短路径*/
{
  queue p;
  int kill[MaxX][MaxY]={0};  /*判断是否是回路*/
  int i=1,j=1,n;        /*i、j用于记录所走的下标，n用来计算搜索的方向个数（8个）*/
  int po;          /*检查方向的计数器*/
  if(Map[X][Y]&&Map[i][j])
    return;      /*如果入口或出口不通直接返回*/
  do
    {
       if(!Map[i][j]&&!kill[i][j]) /*如果是通路且未访问过*/
         {
            en_queue(i,j);    /*将要可通行的坐标入队*/
     kill[i][j]=1;     /*将判断标志改为1*/
     mouse(i,j); /*画当前位置*/
            TIMEDELAY();   /*延时*/
     erasermouse(i,j);    /*擦除所走过的点*/
     if(!Map[i][j])      /*是通路的情况*/
              {
                i = i+1;     /*下一个要检查的坐标 左斜上方*/
                j = j+1;
              }
            po=0;      /*计数器清零*/
        }
      else
        {
    i=result->data[result->rear-1].x;    /*回溯*/
           j=result->data[result->rear-1].y;
           for(n=0;n<7;n++)  /*在上面if语句中已经判断了一个方向，所以只要再搜索其余的7个方向即可*/
             {
               po++;
               if(po==1)
                 {
                   j++;         /*右*/
                   if(!Map[i][j]&&!kill[i][j])
                     break;
                   else
                     j--;
                 }
               if(po==2)
                 {
                   i++;      /*下*/
                   if(!Map[i][j]&&!kill[i][j])
                     break;
                   else
                     i--;
                  }
                if(po==3)
                  {
                    i--;j++;    /*右斜上*/
                    if(!Map[i][j]&&!kill[i][j])
                      break;
                    else
                      {
                        i++;
                        j--;
                      }
                  }
                 if(po==4)
                   {
                     i++;j--;    /*左斜下*/
                     if(!Map[i][j]&&!kill[i][j])
                       break;
                     else
                       {
                         i--;
                         j++;
                       }
                   }
                 if(po==5)
                   {
                     i--;    /*上*/
                     if(!Map[i][j]&&!kill[i][j])
                       break;
                     else
                       i++;
                   }
                  if(po==6)
                    {
                      j--;          /*左*/
                      if(!Map[i][j]&&!kill[i][j])
                        break;
                      else
                        j++;
                    }
                  if(po==7)
                    {
                      i--;j--;    /*左斜上*/
                      if(!Map[i][j]&&!kill[i][j])
                        break;
                      else
                        {
                          i++;
                          j++;
                        }
                    }
                 }
           if(n==7&&kill[i][j])  /*下一步没有通路*/
             {
               p=del();  /*将刚入队的下标删除*/
               i=p.x;    /*回溯*/
               j=p.y;
               po=0;  /*清零计数器*/
      }
    if(empty_queue())  /*如果队列为空，则返回*/
      return;
        }
    }while(i!=X+1||j!=Y+1);  /*还没到达迷宫边缘继续循环*/
}
void maze()    /*画迷宫*/
{
  int i,j;
  setbkcolor(5);  /*将背景颜色设置为红紫色*/
  setcolor(14);   /*将当前颜色设置成黄色*/
  rectangle(90,50,90+Y*30,50+X*30);  /*画起点是（90，50）终点是（90+Y*30,50+X*30）的框*/
  for(i=80;i<50+X*30;i=i+30)    /*画迷宫的行 */
    line(90,i,90+Y*30,i);
  for(i=120;i<90+Y*30;i=i+30)   /*画迷宫的列*/
    line(i,50,i,50+X*30);
  for(i=1;i<=X;i++)
   {
     for(j=1;j<=Y;j++)
       if(Map[i][j]==0)
  floodfill(105+(j-1)*30,65+(i-1)*30,14); /*通路的地方变成白色*/
   }
}
void print_path()   /*打印迷宫路径*/
{
  if(result->rear==result->front)
      printf("\n\t\t此迷宫没有出路");
  else
    {
      printf("\n入口->");
      while(result->front!=result->rear)
        {
   printf("(%d,%d)->",result->data[result->front].x,result->data[result->front].y);
          result->front++;
        }
      printf("出口");
    }
}
int menu_select()  /*菜单*/
{
  int sn;
  clrscr();
  printf("\n\t\t迷宫问题\n");
  printf("\n\t\t*********************");
  printf("\n\t\t1.手动绘制迷宫");
  printf("\n\t\t2.电脑绘制迷宫");
  printf("\n\t\t3.退出");
  printf("\n\t\t*********************");
  printf("\n\t\t请选择：");
  scanf("%d",&sn);
  return sn;
}
main()
{
  char k='y',ch;
  int driver=VGA,mode=VGAHI,i;
  while(k=='y')
    {
      switch(menu_select())
        {
           case 1:
                  clrscr();
                  printf("\n请输入迷宫大小X(行1<X<12)Y(列1<Y<12)!\n");
                  scanf("%d%d",&X,&Y);
                  Setmap();   /*手动创建迷宫*/
                  clrscr();  /*清屏*/
                  initgraph(&driver,&mode,"");  /*切换到图形模式*/
                  maze();    /*画迷宫*/
                  SearchWay();   /*找路径*/
                  closegraph();  /*切换到文本模式*/
                  print_path();   /*打印路径*/
                  printf("\n\t\t请按回车返回菜单！\n");
                  fflush(stdin);
                  scanf("%c",&ch);
                  if(ch=='\n')
                    break;
           case 2:
                  clrscr();
                  printf("\n请输入迷宫大小(最好不要超过12行12列)X(行1<X<12),Y(列1<Y<12)!\n");
                  scanf("%d%d",&X,&Y);
                  AutoSetMap();  /*电脑创建迷宫*/
                  clrscr();  /*清屏*/
                  initgraph(&driver,&mode,"");  /*切换到图形模式*/
                  maze();  /*画迷宫*/
                  SearchWay();  /*找路径*/
                  closegraph();   /*切换到文本模式*/
                  print_path();  /*打印路径*/
                  printf("\n\t\t请按回车返回菜单！\n");
                  fflush(stdin);
                  scanf("%c",&ch);
                  if(ch=='\n')
                    break;
           case 3:
                  printf("\n\t\t欢迎下次使用，再见！");
                  k='n';
                  fflush(stdin);
                  scanf("%c",&ch);
                  if(ch=='\n')
                    break;
        }
    }
}