/* algo3-11.c 利用非循環(huán)順序隊(duì)列采用廣度搜索法求解迷宮問(wèn)題(一條路徑) */
 #include"c1.h"
 #define M 5 /* 迷宮行數(shù)(包括外墻) */
 #define N 5 /* 迷宮列數(shù)(包括外墻) */
 #define D 8 /* 移動(dòng)方向數(shù),只能取4和8。(8個(gè),可斜行;4個(gè),只可直走) */

 typedef struct /* 定義隊(duì)列元素和棧元素為同類(lèi)型的結(jié)構(gòu)體 */
 {
   int x,y; /* 當(dāng)前點(diǎn)的行值，列值 */
   int pre; /* 前一點(diǎn)在隊(duì)列中的序號(hào) */
 }QElemType,SElemType; /* 定義棧元素和隊(duì)列元素 */
 #include"c3-1.h" /* 棧的存儲(chǔ)結(jié)構(gòu) */
 #include"bo3-1.c" /* 棧的基本操作 */
 #include"c3-3.h" /* 隊(duì)列的存儲(chǔ)結(jié)構(gòu) */
 #include"bo3-4.c" /* 隊(duì)列的基本操作 */

 struct /* 移動(dòng)數(shù)組,移動(dòng)方向由正東起順時(shí)針轉(zhuǎn) */
 {
   int x,y;
 #if D==8
 }move[D]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};
 #endif
 #if D==4
 }move[D]={{0,1},{1,0},{0,-1},{-1,0}};
 #endif

 Status Path(int maze[M][N]) /* 廣度搜索法求一條迷宮路徑 */
 {
   SqQueue q; /* 采用非循環(huán)順序隊(duì)列 */
   QElemType qf,qt; /* 當(dāng)前點(diǎn)和下一點(diǎn) */
   SqStack s; /* 采用順序棧 */
   int i,j,flag=1; /* 當(dāng)找到出口,flag=0 */
   int x1,y1; /* 終點(diǎn)的坐標(biāo) */
   printf("請(qǐng)輸入入口的行,列(左上角為1,1)\n");
   scanf("%d,%d",&qf.x,&qf.y);
   printf("請(qǐng)輸入出口的行,列(右下角為%d,%d)\n",M-2,N-2);
   scanf("%d,%d",&x1,&y1);
   qf.pre=-1; /* 設(shè)入口(第一點(diǎn))的上一點(diǎn)的序號(hào)=-1 */
   maze[qf.x][qf.y]=-1; /* 初始點(diǎn)設(shè)為-1(已訪(fǎng)問(wèn)過(guò)) */
   InitQueue(&q);
   EnQueue(&q,qf); /* 起點(diǎn)入隊(duì) */
   while(!QueueEmpty(q)&&flag)
   { /* 隊(duì)列中還有沒(méi)被廣度搜索過(guò)的點(diǎn)且還沒(méi)找到出口 */
     DeQueue(&q,&qf); /* 出隊(duì)qf為當(dāng)前點(diǎn) */
     for(i=0;i<D;i++) /* 向各個(gè)方向嘗試 */
     {
       qt.x=qf.x+move[i].x; /* 下一點(diǎn)的坐標(biāo) */
       qt.y=qf.y+move[i].y;
       if(maze[qt.x][qt.y]==1)
       { /* 此點(diǎn)是通道且不曾被訪(fǎng)問(wèn)過(guò) */
         maze[qt.x][qt.y]=-1; /* 已訪(fǎng)問(wèn)過(guò) */
         qt.pre=q.front-1; /* 上一點(diǎn)處于隊(duì)列中現(xiàn)隊(duì)頭減一的位置(沒(méi)刪除) */
         EnQueue(&q,qt); /* 入隊(duì) */
         if(qt.x==x1&&qt.y==y1) /* 到達(dá)終點(diǎn) */
         {
           flag=0;
           break;
         }
       }
     }
   }
   if(flag) /* 搜索完整個(gè)隊(duì)列還沒(méi)到達(dá)終點(diǎn) */
   {
     printf("沒(méi)有路徑可到達(dá)終點(diǎn)！\n");
     return ERROR;
   }
   else
   {
     InitStack(&s); /* 初始化s棧 */
     i=q.rear-1; /* i為待入棧元素在隊(duì)列中的位置 */
     while(i>=0) /* 沒(méi)到入口 */
     {
       Push(&s,*(q.base+i));
       i=(*(q.base+i)).pre; /* i為前一元素在隊(duì)列中的位置 */
     }
     i=0; /* i為走出迷宮的步驟 */
     while(!StackEmpty(s))
     {
       Pop(&s,&qf);
       i++;
       maze[qf.x][qf.y]=i;
     }
     printf("走出迷宮的一個(gè)方案：\n");
     for(i=1;i<M-1;i++) /* 輸出maze[][],其值是走出迷宮的步驟 */
     {
       for(j=1;j<N-1;j++)
         printf("%3d",maze[i][j]);
       printf("\n");
     }
     return OK;
   }
 }

 void main()
 {
   int i,j;
   int maze[M][N]; /* 迷宮數(shù)組 */
   printf("%d行%d列迷宮(不包括外墻)\n",M-2,N-2);
   for(i=0;i<N;i++)
   { /* 0為墻,1為通道 */
     maze[0][i]=0; /* 北墻 */
     maze[M-1][i]=0; /* 南墻 */
   }
   for(i=1;i<M-1;i++)
   {
     maze[i][0]=0; /* 西墻 */
     maze[i][N-1]=0; /* 東墻 */
   }
   printf("請(qǐng)按行輸入迷宮結(jié)構(gòu)(不包括周邊,0為墻,1為通道),如1 0 0 1\n");
   for(i=1;i<M-1;i++)
     for(j=1;j<N-1;j++)
       scanf("%d",&maze[i][j]);
   printf("迷宮結(jié)構(gòu)(包括外墻):\n");
   for(i=0;i<M;i++)
   {
     for(j=0;j<N;j++)
       printf("%3d",maze[i][j]);
     printf("\n");
   }
   Path(maze);
 }