算法 7.6.txt

数据结构各种算法原代码及图形示例

算法 7.6
bool ShortestPath(int maze[][], int m,  int n，Stack &S)
{
   // 求m行n列的迷宫maze中从入口[0][0]到出口[m-1][n-1]的最短路径，
   // 若存在，则返回TRUE，此时栈S中从栈顶到栈底为最短路径所经过的各
   // 个方位;若该迷宫不通，则返回FALSE，此时栈S为空栈。
  DLinkQueue Q;
  bool visited[m][n];
  InitQueue(Q);                          // 队列初始化
  for(i=0; i<m;  i++)                    // 对访问标志数组置初值
     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); // 入口顶点入队列
  found = FALSE;
  while(!found && !QueueEmpty(Q)) {
     GetHead(Q, curpos);                  // 取当前的队头顶点curpos
     for (v=0; v<8,!found; v++) {         // 搜索8个方向的邻接点
       npos = NextPos(curpos, v);
                            // 类型为PosType的npos是搜索到的下一点
       if (Pass(npos)) {    // 如果下一点可走通则入队列  
          EnQueue(Q, npos);
          visited[npos.xpos][npos.ypos] = TRUE;         // 置到访标志
       }//if
       if (npos.xpos=n-1 && npos.ypos=m-1) found=TRUE; // 找到出口
     }//for
     DeQueue(Q);                    // 出队列，准备从下一邻接点搜索
  }//while
  if (found) {
      InitStack(S);         // 栈初始化
      p = Q.rear;           // 从出口顶点以pre指针为导向，反向查看
      while(!p) {
         Push(S,p->seat);   // 把属于最短路径的顶点压入栈中
         p=p->pre;
      }//while
      return TRUE;
  }//if
  else  return FALSE;
}//ShortestPath

在算法7.6中，Pass()为判断迷宫通或阻的函数。