// algo3-5.cpp 利用棧求解迷宮問題(只輸出一個(gè)解，算法3.3)
 #include"c1.h"
 #include"func3-1.cpp"

 int curstep=1; // 當(dāng)前足跡，初值(在入口處)為1
 struct SElemType // 棧的元素類型
 {
   int ord; // 通道塊在路徑上的＂序號(hào)＂
   PosType seat; // 通道塊在迷宮中的＂坐標(biāo)位置＂
   int di; // 從此通道塊走向下一通道塊的＂方向＂(0～3表示東～北)
 };

 #include"c3-1.h" // 采用順序棧存儲(chǔ)結(jié)構(gòu)
 #include"bo3-1.cpp" // 采用順序棧的基本操作函數(shù)

 // 定義墻元素值為0，可通過路徑為1，不能通過路徑為-1，通過路徑為足跡
 Status Pass(PosType b)
 { // 當(dāng)迷宮m的b點(diǎn)的序號(hào)為1(可通過路徑)，返回OK；否則，返回ERROR
   if(m[b.x][b.y]==1)
     return OK;
   else
     return ERROR;
 }

 void FootPrint(PosType a)
 { // 使迷宮m的a點(diǎn)的值變?yōu)樽阚E(curstep)
   m[a.x][a.y]=curstep;
 }

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

 void MarkPrint(PosType b)
 { // 使迷宮m的b點(diǎn)的序號(hào)變?yōu)?1(不能通過的路徑)
   m[b.x][b.y]=-1;
 }

 Status MazePath(PosType start,PosType end) // 算法3.3
 { // 若迷宮m中存在從入口start到出口end的通道，則求得一條
   // 存放在棧中(從棧底到棧頂)，并返回TRUE；否則返回FALSE
   SqStack S; // 順序棧
   PosType curpos; // 當(dāng)前位置
   SElemType e; // 棧元素
   InitStack(S); // 初始化棧
   curpos=start; // 當(dāng)前位置在入口
   do
   {
     if(Pass(curpos))
     { // 當(dāng)前位置可以通過，即是未曾走到過的通道塊
       FootPrint(curpos); // 留下足跡
       e.ord=curstep;
       e.seat=curpos;
       e.di=0;
       Push(S,e); // 入棧當(dāng)前位置及狀態(tài)
       curstep++; // 足跡加1
       if(curpos.x==end.x&&curpos.y==end.y) // 到達(dá)終點(diǎn)(出口)
         return TRUE;
       NextPos(curpos,e.di); // 由當(dāng)前位置及移動(dòng)方向，確定下一個(gè)當(dāng)前位置
     }
     else
     { // 當(dāng)前位置不能通過
       if(!StackEmpty(S)) // 棧不空
       {
         Pop(S,e); // 退棧到前一位置
         curstep--; // 足跡減1
         while(e.di==3&&!StackEmpty(S)) // 前一位置處于最后一個(gè)方向(北)
         {
           MarkPrint(e.seat); // 在前一位置留下不能通過的標(biāo)記(-1)
           Pop(S,e); // 再退回一步
           curstep--; // 足跡再減1
         }
         if(e.di<3) // 沒到最后一個(gè)方向(北)
         {
           e.di++; // 換下一個(gè)方向探索
           Push(S,e); // 入棧該位置的下一個(gè)方向
           curstep++; // 足跡加1
           curpos=e.seat; // 確定當(dāng)前位置
           NextPos(curpos,e.di); // 確定下一個(gè)當(dāng)前位置是該新方向上的相鄰塊
         }
       }
     }
   }while(!StackEmpty(S));
   return FALSE;
 }

 void main()
 {
   Init(1); // 初始化迷宮，通道值為1
   if(MazePath(begin,end)) // 有通路
   {
     printf("此迷宮從入口到出口的一條路徑如下:\n");
     Print(); // 輸出此通路
   }
   else
     printf("此迷宮沒有從入口到出口的路徑\n");
 }