软件综合实习
{ 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; }
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]==\//判断新位置是否可达 { Temp1.x=x; //把可行路径的行x、列y坐标赋给Temp Temp1.y=y;
maze[x][y]=\//标志新位置已到达过 q.Push(Temp1); //新位置入栈【临时栈q】 }
if((x==c1)&&(y==d1)) //成功到达出口
信息科学与工程学院 - 10- 网络工程11-1班
软件综合实习
{ 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)
//如果没有新位置入栈，则返回到上一个位置
{
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的顶点元素，即第一个位置 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; //方向向下，用1表示 }
else if(b==1)
{ temp->data.dir=2; //方向向右，用2表示 }
else if(a==-1)
{ temp->data.dir=3; //方向向上，用3表示 }
else if(b==-1)
信息科学与工程学院 - 11- 网络工程11-1班
软件综合实习
{ temp->data.dir=4; //方向向左，用4表示 }
t.Push(temp->data); //把新位置入栈 delete temp; }
/* *****************************************************************
以下15行代码的作用是，把t赋给x和y。 x的作用是：赋给z（下面定义），提出输出迷宫的路径信息的栈。 y的作用是：定义迷宫通路的指向，提出输出迷宫二维图的栈。
********************************************************************* */ Stack x,y; LinkNode *w,*k;
w=new LinkNode; //申请空间 k=new LinkNode; //申请空间 while(!t.empty())
{ w->data=t.Pop(); //取栈p的顶点元素，即第一个位置 k->data=w->data;
x.Push(w->data); //第一个位置入栈t y.Push(k->data); delete w; delete k;
w=new LinkNode; //重新申请空间 k=new LinkNode; //重新申请空间 }
//╞╪╪╪╪╪╪╪【给可达的通路赋与行走方向】╪╪╪╪╪╪╪╪╪╪╪╪╡ while(!y.empty()) { data=y.Pop();
if(data.dir==1) maze[data.x][data.y]=\↓\ else if(data.dir==2)
maze[data.x][data.y]=\→\ else if(data.dir==3)
maze[data.x][data.y]=\↑\ else if(data.dir==4)
maze[data.x][data.y]=\←\ }
Stack z; //把x反向赋给z。（从z的栈顶是入口坐标） LinkNode *u;
u=new LinkNode; //申请空间 while(!x.empty())
{ u->data=x.Pop(); //取栈p的顶点元素，即第一个位置 z.Push(u->data); //第一个位置入栈t delete u;
u=new LinkNode; //重新申请空间
信息科学与工程学院 - 12- 网络工程11-1班
软件综合实习
} cout<<\《恭喜》！迷宫路径探索成功!\\n\\n\
printf(\┣━━━━━━━━━【迷宫路径输出】━━━━━━━━━┫ \\n\
printf(\┃ ┃ \\n\
printf(\┃ ⑴〖输出迷宫的二维图〗 ┃ \\n\
printf(\┃ ⑵〖输出迷宫的路径〗 ┃ \\n\
printf(\┃ ⑶〖重新输入迷宫路径〗 ┃ \\n\
printf(\┃ ⑷〖退空屏幕〗 ┃ \\n\
printf(\┃ ⑸〖结束探索〗 ┃ \\n\
printf(\┃ ┃ \\n\
printf(\┣━━━━━━━━━━━━━━━━━━━━━━━━━━┫ \\n\
printf(\ while(1) { int j;
printf(\【请选择】操作：\ scanf(\ printf(\ switch(j) {
case 1:
{ int i=0,j=0,count=0;
cout<<\【输出】迷宫的方阵为： \\n\ cout<<\
for(int c=0;c cout< cout< cout< for(i=0;i for(j=0;j if(maze[i][j]==\ 信息科学与工程学院 - 13- 网络工程11-1班 软件综合实习 maze[i][j]=48; maze[a1][b1]=\入\ maze[c1][d1]=\出\ if(maze[i][j]==\ cout<<\ cout< if(count%(n+2)==0) { r++; cout< cout< cout<<\【■：围墙，入：入口，→:向右走，↓：向下走，←：向左走，↑：向上走 】\\n\\n\ break; } case 2: { cout<<\【输出】迷宫的路径为：\\n\\n\ while(!z.empty()) //栈非空，循环输出路径，包括行坐标、列坐标、下一个位置方向 { data=z.Pop(); cout<<\ //输出行x坐标，列y坐标 switch(data.dir) //用循环输出相应的方向 { case 1: cout<<\↓)\\n\ break; case 2: cout<<\→)\\n\ break; case 3: cout<<\↑)\\n\ break; case 4: cout<<\←)\\n\ break; case 0: cout<<\ break; } 信息科学与工程学院 - 14- 网络工程11-1班