/* algo3-9.c 用遞歸函數求解迷宮問題(求出所有解) */
 #include<stdio.h> /* 根據《PASCAL程序設計》(鄭啟華編著)中的程序改編 */
 struct PosType /* 迷宮坐標位置類型 */
 {
   int x; /* 行值 */
   int y; /* 列值 */
 };

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

 /* 全局變量 */
 struct PosType end; /* 迷宮終點位置 */
 MazeType m; /* 迷宮數組 */
 int x,y; /* 迷宮行數，列數 */

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

 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");
   }
   printf("\n");
 }

 void Try(struct PosType cur,int curstep)
 { /* 由當前位置cur、當前步驟curstep試探下一點 */
   int i;
   struct PosType next; /* 下一個位置 */
   struct PosType direc[4]={{0,1},{1,0},{0,-1},{-1,0}}; /* {行增量,列增量} */
   /* 移動方向,依次為東南西北 */
   for(i=0;i<=3;i++) /* 依次試探東南西北四個方向 */
   {
     next.x=cur.x+direc[i].x;
     next.y=cur.y+direc[i].y;
     if(m[next.x][next.y]==-1) /* 是通路 */
     {
       m[next.x][next.y]=++curstep;
       if(next.x!=end.x||next.y!=end.y) /* 沒到終點 */
         Try(next,curstep); /* 試探下一點(遞歸調用) */
       else
         Print(x,y); /* 輸出結果 */
       m[next.x][next.y]=-1; /* 恢復為通路，試探下一條路 */
       curstep--;
     }
   }
 }

 void main()
 {
   struct PosType begin;
   int i,j,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);
   if(j)
     printf("請依次輸入迷宮內墻每個單元的行數,列數：\n");
   for(i=1;i<=j;i++)
   {
     scanf("%d,%d",&x1,&y1);
     m[x1][y1]=0;
   }
   printf("迷宮結構如下:\n");
   Print(x,y);
   printf("請輸入起點的行數,列數：");
   scanf("%d,%d",&begin.x,&begin.y);
   printf("請輸入終點的行數,列數：");
   scanf("%d,%d",&end.x,&end.y);
   m[begin.x][begin.y]=1;
   Try(begin,1); /* 由第一步起點試探起 */
 }