/* algo3-5.c 利用棧求解迷宮問題（只輸出一個解，算法3.3） */
 typedef struct /* 迷宮坐標位置類型 */
 {
   int x; /* 行值 */
   int y; /* 列值 */
 }PosType;

 #define MAXLENGTH 25 /* 設迷宮的最大行列為25 */
 typedef int MazeType[MAXLENGTH][MAXLENGTH]; /* 迷宮數組[行][列] */

 /* 全局變量 */
 MazeType m; /* 迷宮數組 */
 int curstep=1; /* 當前足跡,初值為1 */

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

 #include"c1.h"
 #include"c3-1.h" /* 采用順序棧存儲結構 */
 #include"bo3-1.c" /* 采用順序棧的基本操作函數 */

 /* 定義墻元素值為0,可通過路徑為1,不能通過路徑為-1,通過路徑為足跡 */

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

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

 PosType 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;
   return c;
 }

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

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

 void Print(int x,int y)
 { /* 輸出迷宮的解 */
   int i,j;
   for(i=0;i<x;i++)
   {
     for(j=0;j<y;j++)
       printf("%3d",m[i][j]);
     printf("\n");
   }
 }

 void main()
 {
   PosType begin,end;
   int i,j,x,y,x1,y1;
   printf("請輸入迷宮的行數,列數(包括外墻)：");
   scanf("%d,%d",&x,&y);
   for(i=0;i<x;i++) /* 定義周邊值為0(同墻) */
   {
     m[0][i]=0; /* 行周邊 */
     m[x-1][i]=0;
   }
   for(j=1;j<y-1;j++)
   {
     m[j][0]=0; /* 列周邊 */
     m[j][y-1]=0;
   }
   for(i=1;i<x-1;i++)
     for(j=1;j<y-1;j++)
       m[i][j]=1; /* 定義通道初值為1 */
   printf("請輸入迷宮內墻單元數：");
   scanf("%d",&j);
   printf("請依次輸入迷宮內墻每個單元的行數,列數：\n");
   for(i=1;i<=j;i++)
   {
     scanf("%d,%d",&x1,&y1);
     m[x1][y1]=0; /* 定義墻的值為0 */
   }
   printf("迷宮結構如下:\n");
   Print(x,y);
   printf("請輸入起點的行數,列數：");
   scanf("%d,%d",&begin.x,&begin.y);
   printf("請輸入終點的行數,列數：");
   scanf("%d,%d",&end.x,&end.y);
   if(MazePath(begin,end)) /* 求得一條通路 */
   {
     printf("此迷宮從入口到出口的一條路徑如下:\n");
     Print(x,y); /* 輸出此通路 */
   }
   else
     printf("此迷宮沒有從入口到出口的路徑\n");
 }