迷宫 最短路径及所有路径的问题.doc

#includeusing 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; /迷宫数组 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请选择你要的操作：n 1.使用系统自带迷宫n 2.使用新建迷宫n0.退出n;couti;switch(i)case 1: Init_maze();Migong();break;case 2: NewCreat();Migong();break;case 0: return;default :cout*输入错误，请重新输入！*n;break;/主函数void Init_maze()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;maze65=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 0.返回上一级菜单n; couti;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;i2*m1;i+)cout_;coutendl;for(i=1;im1;i+)for(int j=1;jn1;j+)cout mazeij;coutendl;for(i=1;i2*m1;i+)cout-;coutendl;cout共m1-1行，n1-1列endl;/输出迷宫的图形void Put_in()int p,q;PutOut_Grap();coutpq;i1=p;j1=q;coutpq;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(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+)cout(Stackk.i,Stackk.j);if(k+1)%5=0)coutendl;coutendl;if(top+1minlen)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(di4&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最短路径如下：n长度：minlenendl;cout路径：n(Path0.i,Path0.j);for(k=1;kminlen;k+)cout(Pathk.i,Pathk.j);if(k+1)%5=0)coutendl;coutendl;count=1;cout*n;/输出所有路径void NewCreat()int h,l,i;cout-n;couthl;m1=h+1;n1=l+1;for(i=0;i=m1;i