// algo3-11.cpp 利用非循環順序隊列采用廣度搜索法求解迷宮問題(一條路徑)
 #include"c1.h"
 #include"func3-1.cpp"
 #define D 8 // 移動方向數，只能取4和8。(8個，可斜行；4個，只可直走)

 typedef struct // 定義隊列元素和棧元素為同類型的結構體
 {
   PosType seat; // 當前點的行值，列值
   int pre; // 前一點在隊列中的序號
 }QElemType,SElemType; // 棧元素和隊列元素
 #include"c3-1.h" // 棧的存儲結構
 #include"bo3-1.cpp" // 棧的基本操作
 #include"c3-4.h" // 隊列的存儲結構
 #include"bo3-4.cpp" // 非循環順序隊列的基本操作(1)
 #include"bo3-9.cpp" // 非循環順序隊列的基本操作(2)

 struct // 移動數組，移動方向由正東起順時針轉
 {
   int x,y;
 }move[D]={
 #if D==8
	   {0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};
 #endif
 #if D==4
	   {0,1},{1,0},{0,-1},{-1,0}};
 #endif

 void Path()
 { // 廣度搜索法求一條迷宮路徑
   SqQueue2 q; // 采用非循環順序隊列
   QElemType qf,qt; // 當前點和下一點
   SqStack s; // 采用順序棧
   int i,flag=1; // 當找到出口，flag=0
   qf.seat.x=begin.x; // 將入口作為當前點
   qf.seat.y=begin.y;
   qf.pre=-1; // 設入口(第一點)的上一點的序號=-1
   m[qf.seat.x][qf.seat.y]=-1; // 初始點設為-1(標記已訪問過)
   InitQueue(q);
   EnQueue(q,qf); // 起點入隊
   while(!QueueEmpty(q)&&flag)
   { // 隊列中還有沒被廣度搜索過的點且還沒找到出口
     DeQueue(q,qf); // 出隊qf為當前點
     for(i=0;i<D;i++) // 向各個方向嘗試
     {
       qt.seat.x=qf.seat.x+move[i].x; // 下一點的坐標
       qt.seat.y=qf.seat.y+move[i].y;
       if(m[qt.seat.x][qt.seat.y]==1)
       { // 此點是通道且不曾被訪問過
         m[qt.seat.x][qt.seat.y]=-1; // 標記已訪問過
         qt.pre=q.front-1; // qt的前一點處于隊列中現隊頭減1的位置(沒刪除)
         EnQueue(q,qt); // 入隊qt
         if(qt.seat.x==end.x&&qt.seat.y==end.y) // 到達終點
         {
           flag=0;
           break;
         }
       }
     }
   }
   if(flag) // 搜索完整個隊列還沒到達終點
     printf("沒有路徑可到達終點！\n");
   else // 到達終點
   {
     InitStack(s); // 初始化s棧
     i=q.rear-1; // i為待入棧元素在隊列中的位置
     while(i>=0) // 沒到入口
     {
       Push(s,q.base[i]); // 將隊列中的路徑入棧(棧底為出口，棧頂為入口)
       i=q.base[i].pre; // i為前一元素在隊列中的位置
     }
     i=0; // i為走出迷宮的足跡
     while(!StackEmpty(s))
     {
       Pop(s,qf); // 依照由入口到出口的順序彈出路徑
       i++;
       m[qf.seat.x][qf.seat.y]=i; // 標記路徑為足跡(標記前的值為-1)
     }
     printf("走出迷宮的一個方案：\n");
     Print(); // 輸出m數組
   }
 }

 void main()
 {
   Init(1); // 初始化迷宮，通道值為1
   Path(); // 求一條迷宮路徑
 }