数据结构问题（1）急！！！！！

Question

有一个迷宫，m*n格，0表示可以通过，1表示不能通过，入口为（1，1），出口为（1，n），找出一条从入口到出口的路径，那位大哥能给出一个程序或分析一下算法，最好详细点，给高分！

Answer 1

这要看选择的通过规则了。如象棋中车和马的走法显然不同.
走路规则允许从迷宫的一点其它任何一点的话,走法就是:(1,0)->(1,N)

Answer 2

http://dev.csdn.net/develop/article/25/25075.shtm
http://dev.csdn.net/develop/article/25/25076.shtm

Answer 3

#include<stdlib.h>
#include<fstream.h>
struct InterSection //路口的结构定义
{
int left; //向左
int forward; //向前
int right; //向右
};class Maze
{
private:
int mazeSize; //路口个数
int Exit; //出口
InterSection* intSec; //路口集合
public:
Maze(char *filename);
int TravMaze(int intSecValue); //搜索函数
//~Maze();
};
Maze::Maze(char *filename)
{
ifstream fin;
fin.open(filename,ios::in||ios::nocreate);
if(!fin)
{
cerr<<"数据文件无法打开！";
exit(1);
}
fin>>mazeSize; //读入路口个数
intSec=new InterSection[mazeSize+1];

for(int i=1;i<=mazeSize;i++)
fin>>intSec[i].left>>intSec[i].forward>>intSec[i].right;
fin>>Exit;
fin.close();
}
int Maze::TravMaze(int intSecValue)
{
if(intSecValue>0)
{
if(intSecValue==Exit)
{
cout<<intSecValue<<"<==";
return 1;
}

else if(TravMaze(intSec[intSecValue].left))
{
cout<<intSecValue<<"<==";
return 1;
}
else if(TravMaze(intSec[intSecValue].forward))
{
cout<<intSecValue<<"<==";
return 1;
}
else if(TravMaze(intSec[intSecValue].right))
{
cout<<intSecValue<<"<==";
return 1;
}
}
return 0;
}
void main()
{
char fileName[20]={"Maze.dat"};
Maze m(fileName);
int start=1;
if(m.TravMaze(start))
cout<<endl<<"迷宫的一条路径如上所示：";
else
cout<<"此迷宫无通路:"<<endl;
}

Answer 4

m,n范围未知，不推荐DFS，还是BFS吧。还是那句话，自己看书。

Answer 5

无须递归。用个While就可，注意环线，记住走过的路线，直到端点位置为(1,n)就可。
方法自己去想想就能得到。