//文件名：利用棧求解迷宮問題


 #include"頭文件.h"
 #include"迷宮規模函數.c"

 // 棧的元素類型 
 typedef struct
 {
   int ord;         // 通道塊在路徑上的＂序號＂
   PosType seat;    // 通道塊在迷宮中的＂坐標位置＂
   int di;          // 從此通道塊走向下一通道塊的＂方向＂(0～3表示東～北) 
 }SElemType;        

 #include"棧的存儲結構.h"   // 采用順序棧存儲結構 
 #include"棧的基本操作.c"

 //全局變量
 int curstep=1; // 當前足跡，初值(在入口處)為1 

 //函數聲明
 Status MazePath();       //求從入口到出口的路徑
 Status Pass(PosType b);   //驗證此路是否可通
 void FootPrint(PosType a);   //設定某點為足跡點
 void NextPos(PosType *c,int di);    //根據當前位置和移動方向求出下一個位置
 void MarkPrint(PosType b);        //設定此路為不可通路

 //主函數
 void main()
 {
   Init();    // 初始化迷宮
   if(MazePath())   // 有通路 
   {
     printf("此迷宮從入口到出口的一條路徑如下:\n");
     Print(); // 輸出此通路 
   }
   else
     printf("此迷宮沒有從入口到出口的路徑\n");


 }//main()

 //子函數定義
 Status MazePath() 
 { // 若迷宮m中存在從入口start到出口end的通道，則求得一條存放在棧中(從棧底到棧頂)，并返回TRUE；否則返回FALSE 

   SqStack S;      // 順序棧 
   PosType curpos; // curpos為當前位置 
   SElemType e;    // 棧元素 

   InitStack(&S); // 初始化棧 
   curpos=begin;  // 當前位置在入口 

   do
   {
     if(Pass(curpos))   //當前位置可以通過，即是未曾走到過的通道塊
     {  
       FootPrint(curpos); // 留下足跡 
       e.ord=curstep;
       e.seat=curpos;
       e.di=0;
       Push(&S, e); // 入棧當前位置及狀態 
       curstep++; // 足跡加1 
       if(curpos.x==end.x && curpos.y==end.y) // 到達終點(出口) 
         return TRUE;
       NextPos(&curpos, e.di); // 由當前位置及移動方向，確定下一個當前位置 
     }
     else
     { // 當前位置不能通過 
       if(!StackEmpty(S)) // 棧不空 
       {
         Pop(&S, &e); // 退棧到前一位置 
         curstep--; // 足跡減1 
         while(e.di==3 && !StackEmpty(S)) // 前一位置處于最后一個方向(北) 
         {
           MarkPrint(e.seat); // 在前一位置留下不能通過的標記(-1) 
           Pop(&S, &e); // 再退回一步 
           curstep--; // 足跡再減1 
         } 
         if(e.di<3) // 沒到最后一個方向(北) 
         {
           e.di++; // 換下一個方向探索 
           Push(&S,e); // 入棧該位置的下一個方向 
           curstep++; // 足跡加1 
           curpos=e.seat; // 確定當前位置 
           NextPos(&curpos,e.di); // 確定下一個當前位置是該新方向上的相鄰塊 
         }
       }//end of if(!StackEmpty(S))
     }//end of else
   }while(!StackEmpty(S));

   DestroyStack(&S);//銷毀棧
   return FALSE;
 }//MazePath

 Status Pass(PosType b)
 { // 當迷宮m的b點的序號為1(可通過路徑)，返回OK；否則，返回ERROR 
   if(m[b.x][b.y]==1)
     return OK;
   else
     return ERROR;
 }//Pass

 void FootPrint(PosType a)
 { // 使迷宮m的a點的值變為足跡(curstep) 
   m[a.x][a.y]=curstep;
 }//FootPrint

 void NextPos(PosType *c,int di)
 { // 根據當前位置及移動方向，求得下一位置 
   PosType direc[4]={{0,1},{1,0},{0,-1},{-1,0}}; // {行增量,列增量},移動方向,依次為東南西北 

   (*c).x+=direc[di].x;
   (*c).y+=direc[di].y;
 }//NextPos

 void MarkPrint(PosType b)
 { // 使迷宮m的b點的序號變為-1(不能通過的路徑) 
   m[b.x][b.y]=-1;
 }//MarkPrint