#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;
        }
    }
}