#include<iostream.h>
#include<assert.h>
#include<math.h>
enum Boolean{False,True};
template<class Type> class Stack{
public:
Stack(int =20);
~Stack(){ delete [] element;}
void Push(const Type &item);
Type Pop();
Type GetTop();
void MakeEmpty() { top=-1;}
int IsEmpty() const { return top == -1;}
int IsFull() const { return top==maxSize-1;}
private:
int top;
Type *element;
int maxSize;
};
template<class Type>
Stack<Type>::Stack(int s):top(-1),maxSize(s){
element=new Type[maxSize];
assert(element !=0);
};
template<class Type>
void Stack<Type>::Push(const Type &item){
assert( !IsFull());
element[++top]=item;
}
template<class Type>
Type Stack<Type>::Pop(){
assert(!IsEmpty());
return element[top--];
}
template<class Type>
Type Stack<Type>::GetTop(){
assert(!IsEmpty());
return element[top];
}
void ShowMaze(int maze[10][10]){
int i,j;
for(i=0;i<10;i++){
for(j=0;j<10;j++){
cout<<maze[i][j]<<" ";
}
cout<<endl;
}
}
typedef struct{
int i;//行
int j;//列
}PosType;

typedef struct{
int ord;// 序号
PosType seat;//位置
int di; //方向 1，2，3，4
}SElemType;
int Pass(int maze[10][10],PosType pos)
{
return maze[pos.i][pos.j]==0;
}
void FootPrint(int maze[10][10],PosType pos)
{
maze[pos.i][pos.j]=8;
}
PosType NextPos(int maze[10][10],PosType pos,int di)
{
switch(di){
case 1: pos.j+=1;break;
case 2: pos.i+=1;break;
case 3: pos.j-=1;break;
case 4: pos.i-=1;break;
}
return pos;
}
void MarkPrint(int maze[10][10],PosType pos)
{
maze[pos.i][pos.j]=2;
}
void MazePath(int maze[10][10],PosType start,PosType end)
{
Stack<SElemType> S;
PosType curpos=start;
SElemType e;
int curstep=1;
do{
if(Pass(maze,curpos)){ //当前位置是否是通路
FootPrint(maze,curpos);
e.ord=curstep;
e.seat=curpos;
e.di=1;
S.Push(e);
if(curpos.i == end.i && curpos.j == end.j) return;
curpos=NextPos(maze,curpos,1);
curstep++;
}
else{
if( ! S.IsEmpty()){
e=S.Pop();
while(e.di == 4 && !S.IsEmpty()){
MarkPrint(maze,e.seat); e=S.Pop();
}
if(e.di <4)
e.di++; S.Push(e);
curpos=NextPos(maze,e.seat,e.di);
}
}
}while( ! S.IsEmpty());
return;
}
void main()
{
int Maze[10][10]={
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,1,0,0,0,1},
{1,0,1,1,1,1,0,0,0,1},
{1,0,1,0,1,1,0,1,1,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,1,0,0,1},
{1,1,1,1,1,1,1,1,1,1}
};
ShowMaze(Maze);
PosType start,end;
cout<<"请输入起始坐标 "<<endl;
cin>>start.i; cin>>start.j;
cout<<"请输入终点坐标"<<endl;
cin>>end.i; cin>>end.j;

MazePath(Maze,start,end);

ShowMaze(Maze);
}

这是一条通路的算法,但不是最短路径,哪位朋友能助我一臂之力?