迷宫问题讨论--(堆栈)

一:迷宫问题用堆栈的方法:
求迷宫中一条从入口到出口的路径的算法可简单描述如下:
设定当前位置的初值为入口位置:
do{
    若当前位置可通,
    则{ 将当前位置插入堆栈顶;
        若该位置是出口位置,则结束;
        否则切换当前位置的东邻块为新的当前位置;
      }
    否则,
 若堆栈不空且栈顶位置尚有其他方向未经探索;
  则设定新的当前位置为沿顺时针方向转到的栈顶位置的下一相邻块;
 若栈不空但栈顶位置的四周均不可通,
         则{删去栈顶位置;
     若栈不空,则重新测试新的栈顶位置,
      直至找到一个可通的相邻或出栈至栈空;
           }
    }(栈不空)

typedef struct{
 int ord;               //通道块在路径上的"序号"
 PosType seat;  //通道块在迷宫中的"坐标位置"
 int di;                 //从此通道块走向下一通道块的"方向"
}SElemType;    //堆栈的元素类型

Status MazePath(MazeType maze,PosType start,PosType end)
{
 //若迷宫maze中存在从入口start到出口end的通道,则求得一条存放在栈中(从栈底到栈顶),并返回TRUE;否则返回FALSE
InitStack(S);
curpos=start;   //设定"当前位置"为"入口位置"
curstep=1;   //探索第一步
do{
      if(Pass(curpos)){                                //当前位置可以通过,即是未曾到过的通道.
      FootPrint(curpos);//留下足迹
     e=(curstep,curpos,1);
     Push(S,e);            //加入路径
     if(curpos==end) return(TRUE);//到达终点(出口)
       curpos=NextPos(curpos,1);//下一步是当前位置的东邻
     curstep++;           //探索下一步
    }
    else{                                                   //当前位置不能通过
                 if (!StackEmpty(S)){                      
                                   Pop(S,e);
     while(e.di==4&&!StackEmpty(S)) {
   MarkPrint(e.seat;Pop(S,e));//留下不能通过的标志,并退回一步
                  }
                                    if(e.di<4){
       e.di++;Push(S,e);                         //换下一个方向探索
      curpos=NextPos(e.seat, e.di);   //设定当前位置是该新方向上的相邻块
      }    
                                          }
          }
              }while(!StackEmpty(S));
  return(FALSE);
   }

本文地址：http://com.8s8s.com/it/it28726.htm