算法 7.6
bool ShortestPath(int maze[][], int m,  int n，Stack &S)
{
   // 求m行n列的迷宮maze中從入口[0][0]到出口[m-1][n-1]的最短路徑，
   // 若存在，則返回TRUE，此時(shí)棧S中從棧頂?shù)綏５诪樽疃搪窂剿?jīng)過的各
   // 個(gè)方位;若該迷宮不通，則返回FALSE，此時(shí)棧S為空棧。
  DLinkQueue Q;
  bool visited[m][n];
  InitQueue(Q);                          // 隊(duì)列初始化
  for(i=0; i<m;  i++)                    // 對訪問標(biāo)志數(shù)組置初值
     for(j=0; j<n; j++)  visited[i][j] = FALSE;
  if (maze[0][0]!=0) return FALSE;
  e.xpos = 0;  e.ypos = 0;  EnQueue(Q, e); // 入口頂點(diǎn)入隊(duì)列
  found = FALSE;
  while(!found && !QueueEmpty(Q)) {
     GetHead(Q, curpos);                  // 取當(dāng)前的隊(duì)頭頂點(diǎn)curpos
     for (v=0; v<8,!found; v++) {         // 搜索8個(gè)方向的鄰接點(diǎn)
       npos = NextPos(curpos, v);
                            // 類型為PosType的npos是搜索到的下一點(diǎn)
       if (Pass(npos)) {    // 如果下一點(diǎn)可走通則入隊(duì)列  
          EnQueue(Q, npos);
          visited[npos.xpos][npos.ypos] = TRUE;         // 置到訪標(biāo)志
       }//if
       if (npos.xpos=n-1 && npos.ypos=m-1) found=TRUE; // 找到出口
     }//for
     DeQueue(Q);                    // 出隊(duì)列，準(zhǔn)備從下一鄰接點(diǎn)搜索
  }//while
  if (found) {
      InitStack(S);         // 棧初始化
      p = Q.rear;           // 從出口頂點(diǎn)以pre指針為導(dǎo)向，反向查看
      while(!p) {
         Push(S,p->seat);   // 把屬于最短路徑的頂點(diǎn)壓入棧中
         p=p->pre;
      }//while
      return TRUE;
  }//if
  else  return FALSE;
}//ShortestPath

在算法7.6中，Pass()為判斷迷宮通或阻的函數(shù)。