迷宫-最短路径及所有路径的问题(共11页)

1、精选优质文档-倾情为你奉上#include<iostream>using namespace std;#define MAXSIZE 200#define m 999#define n 999typedef structint i,j,di; Queue;Queue StackMAXSIZE,PathMAXSIZE;/栈和存放最短路径长度的数组 int top=-1,count=1,minlen=MAXSIZE;/栈顶指针，路径计数器，最短路径长度 const int move42= -1,0,0,1,1,0,0,-1; int markmn; /标志数组 int mazemn;

2、/迷宫数组 int i1=1,j1=1,i2=10,j2=10,m1=11,n1=11; /入口，出口坐标，迷宫大小void Init_maze(); /初始化系统自带迷宫void NewCreat(); /新建迷宫void Put_in(); /输入进出口void PutOut_all(); /找所有路径和最短路径并输出所有路径void PutOut_Grap(); /输出迷宫图形void Migong(); /使用迷宫void main()cout<<"*欢迎使用迷宫系统*n"while(1)int i; cout<<"请选择你要的操作

3、：n" <<"1.使用系统自带迷宫n" <<"2.使用新建迷宫n"<<"0.退出n"cout<<"请输入："cin>>i;switch(i)case 1: Init_maze();Migong();break;case 2: NewCreat();Migong();break;case 0: return;default :cout<<"*输入错误，请重新输入！*n"break;/主函数void Init_maze

4、()int i;for(i=0;i<=m1;i+)for(int j=0;j<=n1;j+)mazeij=1;markij=0;for(i=1;i<=6;i+)maze1i=0;maze18=maze21=maze23=0;for(i=6;i<=10;i+)maze2i=0;maze31=maze33=maze36=maze310=0;maze41=maze49=maze410=maze51=0;for(i=3;i<=7;i+)maze4i=0; for(i=1;i<=3;i+)maze6i=0;for(i=7;i<=10;i+)maze6i=0;ma

5、ze65=maze71=maze75=maze76=0;maze77=maze93=maze98=maze910=0;for(i=1;i<=5;i+)maze8i=0;for(i=8;i<=10;i+)maze8i=0;maze108=maze64=maze87=maze1010=0;/构建系统迷宫void Migong()cout<<"*欢迎使用迷宫*n"while(1)int i;cout<<"请选择你要的操作：n" <<" 1.输出所有路径及最短路径n"<<"

6、 0.返回上一级菜单n" cout<<"请输入："cin>>i;cout<<"-n"switch(i)case 1: Put_in();PutOut_all();break;case 0: return;default :cout<<"*输入错误，请重新输入！*n"break;/系统自带迷宫操作函数void PutOut_Grap()int i; cout<<"迷宫图形："<<endl;for(i=1;i<2*m1;i+)cou

7、t<<"_"cout<<endl;for(i=1;i<m1;i+)for(int j=1;j<n1;j+)cout<<" "<<mazeij;cout<<endl;for(i=1;i<2*m1;i+)cout<<"-"cout<<endl;cout<<"共"<<m1-1<<"行，"<<n1-1<<"列"<<

8、;endl;/输出迷宫的图形void Put_in()int p,q;PutOut_Grap();cout<<"请选择你的入口（i1,j1）："cin>>p>>q;i1=p;j1=q;cout<<"请选择你的出口（i2,j2）："cin>>p>>q;i2=p;j2=q;/输入迷宫的进出口void PutOut_all()int i,j,di,find,k;top+;Stacktop.i=i1;Stacktop.j=j1;Stacktop.di=-1;marki1j1=1;while(

9、top>-1) /寻找路径i=Stacktop.i;j=Stacktop.j;di=Stacktop.di;if(i=i2&&j=j2) /找到一条路径则输出cout<<"*n"cout<<"路径"<<count+<<"：n"cout<<"("<<Stack0.i<<","<<Stack0.j<<")"for(k=1;k<=top;k+)co

10、ut<<"->("<<Stackk.i<<","<<Stackk.j<<")"if(k+1)%5=0)cout<<endl;cout<<endl;if(top+1<minlen)for(k=0;k<=top;k+)Pathk=Stackk;minlen=top+1;markStacktop.iStacktop.j=0;top-;i=Stacktop.i;j=Stacktop.j; di=Stacktop.di;find=0;while

11、(di<4&&find=0) /确定将要移动的方向及路程di+;i=Stacktop.i+movedi0;j=Stacktop.j+movedi1;if(markij=0&&mazeij=0)find=1;if(find=1) /若有路可走则进栈Stacktop.di=di;top+;Stacktop.i=i;Stacktop.j=j;Stacktop.di=-1;markij=1;elsemarkStacktop.iStacktop.j=0;top-; cout<<"*n"cout<<"最短路径如下：

12、n"<<"长度："<<minlen<<endl;cout<<"路径：n("<<Path0.i<<","<<Path0.j<<")"for(k=1;k<minlen;k+)cout<<"->("<<Pathk.i<<","<<Pathk.j<<")"if(k+1)%5=0)cout<<endl;cout<<endl;count=1;cout<<"*n"/输出所有路径void NewCreat()int h,l,i;cout<<"-n"cout<<"请输入你的迷宫的行数，列数："cin>>h>>l;m1=h+1;n1=l+1;for(i=0;i<=m1;i+)for(int j=0;j<=n