迷宮-最短路徑及所有路徑的問題(共11頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上#include<iostream>using namespace std;#define MAXSIZE 200#define m 999#define n 999typedef structint i,j,di; Queue;Queue StackMAXSIZE,PathMAXSIZE;/棧和存放最短路徑長度的數(shù)組 int top=-1,count=1,minlen=MAXSIZE;/棧頂指針，路徑計數(shù)器，最短路徑長度 const int move42= -1,0,0,1,1,0,0,-1; int markmn; /標志數(shù)組 int mazemn;

2、/迷宮數(shù)組 int i1=1,j1=1,i2=10,j2=10,m1=11,n1=11; /入口，出口坐標，迷宮大小void Init_maze(); /初始化系統(tǒng)自帶迷宮void NewCreat(); /新建迷宮void Put_in(); /輸入進出口void PutOut_all(); /找所有路徑和最短路徑并輸出所有路徑void PutOut_Grap(); /輸出迷宮圖形void Migong(); /使用迷宮void main()cout<<"*歡迎使用迷宮系統(tǒng)*n"while(1)int i; cout<<"請選擇你要的操作

3、：n" <<"1.使用系統(tǒng)自帶迷宮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;/主函數(shù)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;/構(gòu)建系統(tǒng)迷宮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;/系統(tǒng)自帶迷宮操作函數(shù)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<<"請輸入你的迷宮的行數(shù)，列數(shù)："cin>>h>>l;m1=h+1;n1=l+1;for(i=0;i<=m1;i+)for(int j=0;j<=n