软件综合实习
bool Mazepath(string **maze,int m,int n) //寻找迷宫maze中从（1，1）到（m,n）的路径，如果到则返回true,
否则返回false {
Stack q,p; //定义栈p、q,分别存探索迷宫的过程和存储路径 T Temp1,Temp2; int x,y,loop;
printf(\【请输入】入口行坐标，列坐标：\ cin>>a1>>b1; while(a1>m||b1>n) {
printf(\【输入坐标有误】\
printf(\【请重新输入】入口行坐标，列坐标：\ cin>>a1>>b1; }
printf(\
printf(\【请输入】出口行坐标，列坐标：\ cin>>c1>>d1; while(c1>m||d1>n) {
printf(\【输入坐标有误】\
printf(\【请重新输入】出口行坐标，列坐标：\ cin>>c1>>d1;
信息科学与工程学院 - 35- 网络工程11-1班
软件综合实习
}
printf(\
Temp1.x=a1; Temp1.y=b1;
q.Push(Temp1); //将入口位置入栈
p.Push(Temp1);
maze[a1][b1]=\标志入口位置已到达过
while(!q.empty()) //栈q非空，则反复探索 {
Temp2=q.GetPop(); //获取栈顶元素
if(!(p.GetPop().x==q.GetPop().x&&p.GetPop().y==q.GetPop().y))
{
p.Push(Temp2); //如果有新位置入栈，则把上一个探索的位置存入栈p
}
for(loop=0;loop<4;loop++) //探索当前位置的4个相邻位置
{
x=Temp2.x+move[loop][0]; //计算出新位置行x位置值（move分别=0、1、0、-1）
y=Temp2.y+move[loop][1]; //计算出新位置列y位置值（move分别=1、0、-1、0）
if(maze[x][y]==\判断新位置是否可达
信息科学与工程学院 - 36- 网络工程11-1班
软件综合实习
{
Temp1.x=x; //把可行路径的行x、列y坐标赋给Temp
Temp1.y=y;
maze[x][y]=\标志新位置已到达过
q.Push(Temp1); //新位置入栈【临时栈q】
}
if((x==c1)&&(y==d1)) //成功到达出口
{
Temp1.x=c1; //把出口的行x、列y坐标赋给Temp
Temp1.y=d1; Temp1.dir=0; p.Push(Temp1);
//把最后一个位
置入栈p 出路径
PrintPath(p,m,n,maze); //输
Restore(maze,m,n); //恢复路径 return 1; //表示成功找
到路径
}
}
if(p.GetPop().x==q.GetPop().x&&p.GetPop().y==q.GetPop().y) //如果没有新位置入栈，则返回到上一个位置
信息科学与工程学院 - 37- 网络工程11-1班
软件综合实习
{
p.Pop(); q.Pop();
}
}
return 0; //表示查找失败，即迷宫无路经 }
//╞╪╪╪╪╪╪╪╪╪╪╪╪╪╪【输出路径函数】╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╡
void PrintPath(Stack p,int m,int n,string **maze) //输出路径 {
Stack t; //定义一个栈，按从入口到出口存取路径 int a,b; T data;
LinkNode *temp;
temp=new LinkNode; //申请空间 temp->data=p.Pop(); //取栈p的顶点元素，即第一个位置
信息科学与工程学院 - 38- 网络工程11-1班
软件综合实习
t.Push(temp->data); //第一个位置入栈t
delete temp; //释放空间
while(!p.empty()) //栈p非空，则反复回首转移 {
temp=new LinkNode;
temp->data=p.Pop(); //置，得到行走方向 a=t.GetPop().x-temp->data.x; // b=t.GetPop().y-temp->data.y; // if(a==1) {
temp->data.dir=1; //示
}
else if(b==1) {
temp->data.dir=2; //示 }
else if(a==-1) {
temp->data.dir=3; //示
}
信息科学与工程学院 - 39- 获取下一个位行坐标方向 列坐标方向 方向向下，用1表
方向向右，用2表
方向向上，用3表
网络工程11-1班