迷宫.txt

sfsf szfsz

迷宫求解问题虽然是一类经典问题，但是其实原理并不难，说白了就是栈的应用，我想你可能比我还清楚。^_^ 
你的问题很好解决，由于栈中存储的是迷宫的各个点的位置，这样来说在操作完毕后就可以记载所有走过的道路，而栈中的元素个数就是相当于走过的路的长度，如果你有一点图论的基础，可以了解到，实际上关于路的问题，一般都会涉及到权值问题，所谓权值说白了就是路的长短，在迷宫问题里面，每一个点的权值看作是相同的，这样一来，再栈中的元素个数越少，这条路经就越短，只要在你的程序结构体中定义一个计数器，记载栈中元素的个数，最后比较计数器的大小问题就迎刃而解了。程序的实现并不难，你自己试试吧。

bool FindPath(Position start,Position finish,int &PathLen,Position * &path) 
{ 
if((start.row==finish.row)&&(start.col==finish.col)) //当初末位置相等时停止 
{ 
PathLen=0; 
return true; 
} 
for(int i=0;i<=m+1;i++) //使四周都为1 
grid[0][i]=grid[n+1][i]=1; 
for(i=0;i<=n+1;i++) 
grid[i][0]=grid[i][m+1]=1; 
// Position *offset=new Position[4]; //定义对象的指针表示位置的四周值的变化 
Position offset[4]; 
offset[0].row=0;offset[0].col=1; 
offset[1].row=1;offset[1].col=0; 
offset[2].row=0;offset[2].col=-1; 
offset[3].row=-1;offset[3].col=0; 
int Numofnbrs=4; //相邻的方格数 
Position here,nbr; //定义两个对象，表示初始位置 
here.row=start.row; 
here.col=start.col; 
grid[start.row][start.col]=2; 
Queue<Position> Q;//(100); //待考查的方格队列 
do //标记可达相邻方格 
{ 
for(int i=0;i<Numofnbrs;i++) 
{ 
nbr.row=here.row+offset[i].row; //相邻的方格 
nbr.col=here.col+offset[i].col; 
if(grid[nbr.row][nbr.col]==0) //该方格未标记 
{ 
grid[nbr.row][nbr.col]=grid[here.row][here.col]+1; 
if((nbr.row==finish.row)&&(nbr.col==finish.col)) break; //完成布线（该点的四周） 
Q.EnQueue(nbr); //标式的点进栈 
} 
} 
if((nbr.row==finish.row)&&(nbr.col==finish.col)) break; //全部的布线 
if(Q.Empty()) return false; 
Q.DeQueue(here); //取出下一个考察的方格 
} 
while(true); 
PathLen=grid[finish.row][finish.col]-2; //构造最短的路线 
path=new Position[PathLen]; 
here=finish; 
for(int j=PathLen-1;j>=0;j--) 
{ 
path[j]=here; //？？？？？？ 
for(int i=0;i<=Numofnbrs;i++) //找到前驱位置 
{ 
nbr.row=here.row+offset[i].row; 
nbr.col=here.col+offset[i].col; 
if(grid[nbr.row][nbr.col]==j+2) break; 
} 
here=nbr; //向前移动 
} 
return true; 
} 

这是最短线路的源代码！！