數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)——迷宮求解問(wèn)題(共21頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)：迷宮實(shí)驗(yàn)報(bào)告任務(wù)分配：l 程序員： 主要任務(wù)：負(fù)責(zé)整體的算法設(shè)計(jì)以及程序的主要源代碼的編寫(xiě)。l 測(cè)試員： 主要任務(wù)：負(fù)責(zé)在程序員每完成一個(gè)階段對(duì)程序進(jìn)行挑錯(cuò)，測(cè)試主程序并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行整理分析，最后完成實(shí)驗(yàn)報(bào)告的第三、四部分即測(cè)試結(jié)果與分析探討的內(nèi)容。l 文檔員： 主要任務(wù)：負(fù)責(zé)對(duì)程序及界面的美觀提出改善意見(jiàn)，查找程序的小漏洞，負(fù)責(zé)撰寫(xiě)實(shí)驗(yàn)報(bào)告的第一、二部分即實(shí)驗(yàn)內(nèi)容簡(jiǎn)介與算法描述的內(nèi)容。同時(shí)完成整個(gè)文檔的整合，使整篇報(bào)告排版、文字風(fēng)格統(tǒng)一。一、 簡(jiǎn)介圖的遍歷就是從指定的某個(gè)頂點(diǎn)（稱其為初始點(diǎn)）出發(fā)，按照一定的搜索方法對(duì)圖中的所有頂點(diǎn)各做一次訪問(wèn)過(guò)程

2、。根據(jù)搜索方法不同，遍歷一般分為深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷。本實(shí)驗(yàn)中用到的是廣度優(yōu)先搜索遍歷。即首先訪問(wèn)初始點(diǎn)vi，并將其標(biāo)記為已訪問(wèn)過(guò)，接著訪問(wèn)vi的所有未被訪問(wèn)過(guò)的鄰接點(diǎn)，順序任意，并均標(biāo)記為已訪問(wèn)過(guò)，以此類(lèi)推，直到圖中所有和初始點(diǎn)vi有路徑相通的頂點(diǎn)都被訪問(wèn)過(guò)為止。鑒于廣度優(yōu)先搜索是將所有路徑同時(shí)按照順序遍歷，直到遍歷出迷宮出口，生成的路徑為最短路徑。因此我們采用了廣度優(yōu)先搜索。無(wú)論是深度優(yōu)先搜索還是廣度優(yōu)先搜索，其本質(zhì)都是將圖的二維頂點(diǎn)結(jié)構(gòu)線性化的過(guò)程，并將當(dāng)前頂點(diǎn)相鄰的未被訪問(wèn)的頂點(diǎn)作為下一個(gè)頂點(diǎn)。廣度優(yōu)先搜索采用隊(duì)列作為數(shù)據(jù)結(jié)構(gòu)。本實(shí)驗(yàn)的目的是設(shè)計(jì)一個(gè)程序，實(shí)現(xiàn)手動(dòng)或者自動(dòng)

3、生成一個(gè)n×m矩陣的迷宮，尋找一條從入口點(diǎn)到出口點(diǎn)的通路。具體實(shí)驗(yàn)內(nèi)容如下：選擇手動(dòng)或者自動(dòng)生成一個(gè)n×m的迷宮，將迷宮的左上角作入口，右下角作出口，設(shè)“0”為通路，“1”為墻，即無(wú)法穿越。假設(shè)一只老鼠從起點(diǎn)出發(fā)，目的為右下角終點(diǎn)，可向“上、下、左、右、左上、左下、右上、右下”8個(gè)方向行走。如果迷宮可以走通，則用“”代表“1”，用“”代表“0”，用“”代表行走迷宮的路徑。輸出迷宮原型圖、迷宮路線圖以及迷宮行走路徑。如果迷宮為死迷宮，則只輸出迷宮原型圖。二、 算法說(shuō)明根據(jù)實(shí)驗(yàn)內(nèi)容，本實(shí)驗(yàn)主要設(shè)計(jì)實(shí)現(xiàn)手動(dòng)輸入迷宮，判斷迷宮能否走通；自動(dòng)生成迷宮，判斷迷宮能否走通。迷宮算法的整體

4、思想如下： 1、迷宮的創(chuàng)建迷宮中存在通路和障礙，為了方便迷宮的創(chuàng)建，可用0表示通路，用1表示障礙，這樣迷宮就可以用0、1矩陣來(lái)描述。設(shè)置迷宮的長(zhǎng)為n、寬為m，范圍為49×49，用int mazeN+2M+2來(lái)表示，這樣相當(dāng)于在迷宮外層包了一層1，即防止搜索路徑時(shí)跳出迷宮。（1）手動(dòng)生成迷宮void hand_maze(int m,int n) /手動(dòng)生成迷宮int i,j; for(i=0;i<m;i+) for(j=0;j<n;j+)cin>>mazeij; （2） 自動(dòng)生成迷宮void automatic_maze(int m,int n) /自動(dòng)生成迷宮

5、int i,j;for(i=0;i<m;i+)for(j=0;j<n;j+)mazeij=rand()%2; /隨機(jī)生成0、1maze00=0; /將開(kāi)始和結(jié)束位置強(qiáng)制為0，保證有可能出來(lái)迷宮mazem-1n-1=0;2、迷宮路徑的搜索在生成的0、1矩陣迷宮中，首先從迷宮的入口開(kāi)始，如果該位置就是迷宮出口，則已經(jīng)找到了一條路徑，搜索工作結(jié)束。否則搜索其北（-1，0），東北（-1，-1），東（0,1），東南（1,1），南（1,0），西南（1，-1），西（0，-1），西北（-1，-1）8個(gè)方向位，是否是障礙，若不是障礙，就移動(dòng)到該位置，然后再?gòu)脑撐恢瞄_(kāi)始搜索通往出口的路徑；若是障礙就選

6、擇另一個(gè)相鄰的位置，并從它開(kāi)始搜索路徑。為防止搜索重復(fù)出現(xiàn)，則將已搜索過(guò)的位置標(biāo)記為2，同時(shí)保留搜索痕跡，在考慮進(jìn)入下一個(gè)位置搜索之前，將當(dāng)前位置保存在一個(gè)隊(duì)列中，如果所有相鄰的非障礙位置均被搜索過(guò)，且未找到通往出口的路徑，則表明不存在從入口到出口的路徑。這實(shí)現(xiàn)的是廣度優(yōu)先遍歷的算法，如果找到路徑，則為最短路徑。逆序輸出路徑，將已輸出的路徑標(biāo)記為3。實(shí)驗(yàn)數(shù)據(jù)如下：列 行012300101100102101031100123456789（0,0）（1,1）（1,0）（0,2）（2，1）（1,3）（3,2）（2,3）（3,3）-111223456算法如下：int path(int maze5151

7、,int m,int n) /路徑求解X=1; /初始值定為1struct point p=0,0,-1; /定義入口節(jié)點(diǎn)if(mazep.rowp.col=1) /入口為1時(shí)，迷宮不可解 cout<<"此迷宮無(wú)解nn" X=0; return 0; mazep.rowp.col=2; /標(biāo)記為已訪問(wèn) enqueue(p); /將p入隊(duì)列while(!is_empty() p=dequeue(); if(p.row=m-1)&&(p.col=n-1) /當(dāng)行和列為出口時(shí)跳出 break; /定義8個(gè)走位方向 if(p.row-1)>=0)&

8、amp;&(p.row-1)<m)&&(p.col+0)<n)&&(mazep.row-1p.col+0=0) visit(p.row-1,p.col+0,maze); /北 if(p.row-1)>=0)&&(p.row-1)<m)&&(p.col+1)<n)&&(mazep.row-1p.col+1=0) visit(p.row-1,p.col+1,maze); /東北 if(p.row+0)<m)&&(p.col+1)<n)&&

9、(mazep.row+0p.col+1=0) visit(p.row+0,p.col+1,maze); /東 if(p.row+1)<m)&&(p.col+1)<n)&&(mazep.row+1p.col+1=0) visit(p.row+1,p.col+1,maze); /東南 if(p.row+1)<m)&&(p.col+0)<n)&&(mazep.row+1p.col+0=0) visit(p.row+1,p.col+0,maze); /南 if(p.row+1)<m)&&(p.

10、col-1)<n)&&(p.col-1)>=0)&&(mazep.row+1p.col-1=0) visit(p.row+1,p.col-1,maze); /西南 if(p.row+0)<m)&&(p.col-1)<n)&&(p.col-1)>=0)&&(mazep.row+0p.col-1=0) visit(p.row+0,p.col-1,maze); /西 if(p.row-1)>=0)&&(p.row-1)<m)&&(p.col-1)&

11、lt;n)&&(p.col-1)>=0)&&(mazep.row-1p.col-1=0) visit(p.row-1,p.col-1,maze); /西北if(p.row=m-1&&p.col=n-1) /如果當(dāng)前矩陣點(diǎn)是出口點(diǎn)，輸出路徑 cout<<"迷宮路徑為：n" cout<<"出口"<<endl; cout<<" "<<""<<endl; printf("(%d,%d)n&

12、quot;,p.row+1,p.col+1); cout<<" "<<""<<endl; mazep.rowp.col=3; /逆序?qū)⒙窂綐?biāo)記為3 while(p.predecessor!=-1) p=queuep.predecessor; printf("(%d,%d)n",p.row+1,p.col+1); cout<<" "<<""<<endl; mazep.rowp.col=3; cout<<"

13、入口"<<endl;else cout<<"此迷宮無(wú)解！nn" X=0;return 0;3、 輸出迷宮圖（1）、生成迷宮圖，將迷宮外殼輸出為，將迷宮中的0輸出為，將1輸出為for(k=0;k<n;k+)cout<<"" /這兩個(gè)黑三角用來(lái)生成頂部外殼for(i=0;i<m;i+)cout<<"n"cout<<"" /生成左外殼for(j=0;j<n;j+) if(mazeij=0) cout<<"&quo

14、t;if(mazeij=1) cout<<""cout<<"" /生成右外殼cout<<endl;for(k=0;k<n;k+)cout<<""cout<<" n" /生成底部外殼（2）、生成迷宮路徑圖，for(i=0;i<m;i+)cout<<"n"for(j=0;j<n;j+)if(mazeij=0|mazeij=2) /2是隊(duì)列中訪問(wèn)過(guò)的點(diǎn) cout<<""if(maz

15、eij=1) cout<<""if(mazeij=3) /3是標(biāo)記的可以走通的路徑cout<<""（3）總界面的實(shí)現(xiàn)考慮到添加畫(huà)圖部分，對(duì)我們的原程序改動(dòng)較大，因此我們沒(méi)有采用畫(huà)圖畫(huà)線輸出迷宮路徑，同時(shí)，我們也擴(kuò)充了迷宮的功能，可以定義任意寬度和長(zhǎng)度的迷宮并實(shí)現(xiàn)手動(dòng)、自動(dòng)生成迷宮等功能。輸出界面有三個(gè)選項(xiàng)，1為手動(dòng)生成迷宮，2為自動(dòng)生成迷宮，3為推出程序。當(dāng)程序運(yùn)行時(shí)，設(shè)cycle為0，當(dāng)選擇3退出程序時(shí)，cycle為-1。void main() int i,m,n,cycle=0; while(cycle!=(-1) switc

16、h(i) case 1: /手動(dòng)輸出迷宮 cout<<"n請(qǐng)輸入行數(shù)：" cin>>m; cout<<"n" cout<<"請(qǐng)輸入列數(shù)：" cin>>n; while(m<0|m>49)|(n<0|n>49) cout<<"n抱歉，你輸入的行列數(shù)超出預(yù)設(shè)范圍(0-49,0-49),請(qǐng)重新輸入nn" cout<<"n請(qǐng)輸入行數(shù)：" cin>>m; cout<<&quo

17、t;n" cout<<"請(qǐng)輸入列數(shù)：" cin>>n; shoudong_maze(m,n); data(m,n); print_maze(m,n); mgpath(maze,m,n); if(X!=0) result_maze(m,n); cout<<"nnPress Enter Contiue!n" getchar(); while(getchar()!='n'); break; case 2: /自動(dòng)輸出迷宮 cout<<"n請(qǐng)輸入行數(shù)：" cin>

18、>m; cout<<"n" cout<<"請(qǐng)輸入列數(shù)：" cin>>n; while(m<0|m>49)|(n<0|n>49) cout<<"n抱歉，你輸入的行列數(shù)超出預(yù)設(shè)范圍(0-49,0-49),請(qǐng)重新輸入nn" cout<<"n請(qǐng)輸入行數(shù)：" cin>>m; cout<<"n" cout<<"請(qǐng)輸入列數(shù)：" cin>>n; zidon

19、g_maze(m,n); data(m,n); print_maze(m,n); mgpath(maze,m,n); if(X!=0) result_maze(m,n); cout<<"nnPress Enter Contiue!n" getchar(); while(getchar()!='n'); break; case 3: /程序退出 cycle=(-1);break; default: /其他情況時(shí)，輸出有誤 cout<<"n"cout<<"你的輸入有誤!n" cout&l

20、t;<"nPress Enter Contiue!n" getchar(); while(getchar()!='n'); break; 三 測(cè)試結(jié)果本設(shè)計(jì)采用廣度優(yōu)先的算法，實(shí)現(xiàn)迷宮的路徑求解，在原要求的基礎(chǔ)上，加以擴(kuò)展，實(shí)現(xiàn)要求范圍內(nèi)的N×N,N×M的手動(dòng)、自動(dòng)生成迷宮矩陣的求解。（一） 基本功能測(cè)試1、 手動(dòng)迷宮（1）N×N迷宮路徑求解a）4×4迷宮矩陣: 0 1 0 0 0 0 1 11 0 1 1 1 0 0 11 0 1 1 1 0 1 11 1 0 0 0 1 1 0運(yùn)行后，判定為有解迷宮，輸出如下

21、： 運(yùn)行后，判定為無(wú)解迷宮，輸出如下： （對(duì)符號(hào)解釋的放置） （對(duì)1墻的解釋） b） 7×7迷宮矩陣0 1 0 0 1 0 1 0 1 1 0 1 0 11 0 1 1 0 1 0 1 0 1 1 0 0 10 1 0 0 1 0 1 0 0 0 1 1 0 11 0 1 1 1 1 1 1 1 1 1 1 0 11 1 0 1 0 1 1 0 0 0 0 0 0 01 1 1 0 1 0 1 1 1 0 1 1 0 00 1 1 1 0 0 0 0 0 0 1 0 1 0運(yùn)行后，判定為有解迷宮，輸出如下： 運(yùn)行后，判定為無(wú)解迷宮，輸出如下： （1） N×M迷宮路徑求解（N

22、!=M）a）4×6迷宮矩陣0 1 0 0 1 0 0 1 0 0 1 01 0 1 0 0 1 0 0 0 1 0 11 0 0 1 0 1 1 0 1 0 1 10 1 1 0 1 0 1 1 1 0 1 0運(yùn)行后，判定為有解迷宮，輸出如下: 運(yùn)行后，判定為無(wú)解迷宮，輸出如下： b） 5×3迷宮矩陣0 1 0 0 1 00 1 0 0 0 10 0 1 1 1 00 0 0 1 1 10 1 0 0 1 0運(yùn)行后，判定為有解迷宮，輸出如下: 運(yùn)行后，判定為無(wú)解迷宮，輸出如下: 2、 自動(dòng)迷宮（1） N×N迷宮路徑求解 5×5迷宮矩陣 測(cè)試次數(shù)第一次第二

23、次第三次生成迷宮判斷結(jié)果（2） N×M迷宮矩陣測(cè)試（N!=M）6*8迷宮矩陣測(cè)試次數(shù)第一次第二次第三次生成迷宮判斷結(jié)果（二） 廣度優(yōu)先搜索（BFS）測(cè)試-多通路迷宮折取最優(yōu)。1、 課本實(shí)例 (P68 測(cè)試用例1) 輸出迷宮 輸出結(jié)果 2、自行設(shè)計(jì)手動(dòng)輸入迷宮測(cè)試迷宮全部路徑展示測(cè)試結(jié)果四、分析與探討第三部分中，展示了程序所實(shí)現(xiàn)的各種情況。下面從程序源代碼的角度來(lái)進(jìn)一步分析各算法的時(shí)間復(fù)雜性。1、程序分析（1）手動(dòng)生成迷宮算法：void hand_maze(int m,int n) int i,j;cout<<endl; cout<<"請(qǐng)按行輸入迷宮，

24、0表示通路，1表示障礙:"<<endl; for(i=0;i<m;i+) for(j=0;j<n;j+)cin>>mazeij; 可以看出，該算法的時(shí)間復(fù)雜度為T(mén)(N)=O(N2)。因此，這是一個(gè)線性算法，隨著N的增加，算法的時(shí)間復(fù)雜度線性增加。（2）自動(dòng)生成迷宮算法：void automatic_maze(int m,int n) /自動(dòng)生成迷宮int i,j;cout<<"n迷宮生成中nn"system("pause");for(i=0;i<m;i+)for(j=0;j<n;j+)

25、mazeij=rand()%2; /隨機(jī)生成0、1 maze00=0; mazei-1j-1=0; /首尾置為0，保證迷宮基本功能的實(shí)現(xiàn)時(shí)間復(fù)雜性、度上，該算法同于手動(dòng)生成迷宮算法，為T(mén)（N）=O（N2），也是一個(gè)線性算法，隨著N的增加，算法的時(shí)間復(fù)雜性增加。（3） 輸出迷宮的星號(hào)路徑算法： void result_maze(int m,int n) /打印輸出迷宮的星號(hào)路徑int i,j;printf("迷宮通路(用表示)如下所示：nt");for(i=0;i<m;i+)printf("n");for(j=0;j<n;j+)if(mazei

26、j=0|mazeij=2)printf("");if(mazeij=1)printf("");if(mazeij=3)printf(""); 2、程序討論（1）在程序編寫(xiě)的過(guò)程中，我們發(fā)現(xiàn)了很多問(wèn)題及錯(cuò)誤。例如，程序剛形成雛形時(shí)，經(jīng)測(cè)試，程序只能實(shí)現(xiàn)課本要求的8*8的迷宮矩陣尋路，并且會(huì)出現(xiàn)尋路時(shí)跳出迷宮的情況。因此，程序員在此基礎(chǔ)上，將迷宮矩陣數(shù)組由原來(lái)的maze1010改為mazeN+2M+2，并在相應(yīng)函數(shù)上加以大量改動(dòng)，最終使本程序?qū)崿F(xiàn)了程序本身范圍內(nèi)的任意N*M迷宮矩陣組合的尋路求解。（2）在輸出界面上，起初，僅僅是將最終結(jié)果

27、展示，而無(wú)矩陣的規(guī)范輸出，即如果使用者手輸出迷宮時(shí)，并未整齊的輸入迷宮，如果此時(shí)顯示迷宮最后的路徑，使使用者不易清晰的看出路徑而難以理解?；谡驹谑褂谜叩慕嵌龋尤肓薲ata函數(shù)，實(shí)現(xiàn)了數(shù)組、符號(hào)、數(shù)位路徑、字符路徑共同出現(xiàn)的最終界面，并在輸出時(shí)添加相應(yīng)的箭頭指示，在輸出的迷宮圖時(shí)將最外層加入的圍墻用“”表示，經(jīng)多次修改，使得輸出界面整潔大方。（3）在最開(kāi)始判斷搜索方向的時(shí)候，我們列出的八個(gè)方向并未按照一定順序搜索，此時(shí)就會(huì)出現(xiàn)錯(cuò)誤，后來(lái)采用一定順序來(lái)完成迷宮的搜索，因?yàn)樵O(shè)定迷宮的入口在左上方，出口在右下方，所以采用順時(shí)針?lè)较虮炔捎媚鏁r(shí)針?lè)较蚰茏钕日页鲎疃搪窂健Ｋ宰詈蟛捎昧隧槙r(shí)針的搜索方向，

28、即沿北、東北、東、東南、南、西南、西、西北八個(gè)方向搜索。（4）在測(cè)試輸出結(jié)果方面，出了一個(gè)困擾我們一陣時(shí)間的問(wèn)題，在以5*7自動(dòng)生成迷宮矩陣的測(cè)試過(guò)程中，幾乎每隔幾次都會(huì)出現(xiàn)一次這樣類(lèi)似的問(wèn)題（見(jiàn)下圖），在下圖的輸出界面以及字符展示界面中，經(jīng)過(guò)簡(jiǎn)單的分析，便可以得出最后通往出口的道路，但在程序判斷并輸出路徑后，在圖中可以看到：五角星所標(biāo)記的走過(guò)的路，在出口處出現(xiàn)了錯(cuò)誤。但是此程序手動(dòng)輸入的時(shí)候不會(huì)出現(xiàn)任何錯(cuò)誤，所以問(wèn)題鎖定在自動(dòng)生成迷宮函數(shù)中。在此，我們列出當(dāng)時(shí)的自動(dòng)生成迷宮函數(shù)：void automatic_maze(int m,int n) int i,j;cout<<&quo

29、t;n迷宮生成中nn"system("pause");for(i=0;i<m;i+)for(j=0;j<n;j+)mazeij=rand()%2; maze00=0; mazei-1j-1=0;將此問(wèn)題反映給了程序員，在修改過(guò)程中，反復(fù)分析了各個(gè)函數(shù)后將問(wèn)題鎖定在自動(dòng)生成函數(shù)處。觀察此函數(shù)，發(fā)現(xiàn)“mazei-1j-1=0；”是導(dǎo)致問(wèn)題的最終所在。該語(yǔ)句的初衷是將迷宮矩陣中最初一個(gè)數(shù)判定為0，防止出現(xiàn)迷宮出口不通的情況。在這兒以5*7迷宮為例，經(jīng)過(guò)分析，當(dāng)跳出for循環(huán)時(shí)，i=5，j=6，而要改變的數(shù)是maze57，而非maze56，這也就是導(dǎo)致上圖所示

30、結(jié)果的原因，將該語(yǔ)句改為mazem-1n-1，問(wèn)題解決。3、 程序的前景展望及感想由于時(shí)間匆忙，還有很多功能未能實(shí)現(xiàn)。例如：自動(dòng)生成迷宮時(shí)經(jīng)常出現(xiàn)無(wú)解迷宮，加以改進(jìn)的話，希望可以實(shí)現(xiàn)當(dāng)自動(dòng)生成的迷宮無(wú)解時(shí)，可以自動(dòng)搜索直到出現(xiàn)有解迷宮；或者我們可以實(shí)現(xiàn)操作者可以自己手動(dòng)輸出迷宮路徑等等。在整個(gè)程序設(shè)計(jì)的幾天里，我們?nèi)齻€(gè)同學(xué)分工明確，共同設(shè)計(jì)討論程序，經(jīng)過(guò)多方改進(jìn)與完善，最終完成了此次迷宮的設(shè)計(jì)。附錄 源代碼#include<stdlib.h> /庫(kù)中包含system("pause")和rand()函數(shù)#include<stdio.h> /c語(yǔ)言里的庫(kù)

31、#include<iostream>using namespace std;#define N 49 /定義為全局變量,這是迷宮數(shù)組的上線，可以自行修改#define M 49int X; int mazeN+2M+2;int head=0,tail=0; /隊(duì)列的頭尾指針，初始值設(shè)為0struct point /存放迷宮訪問(wèn)到點(diǎn)的隊(duì)列結(jié)構(gòu)體，包含列，行，序號(hào) int row,col,predecessor; queue1200;void hand_maze(int m,int n) /手動(dòng)生成迷宮int i,j;cout<<endl; cout<<&quo

32、t;請(qǐng)按行輸入迷宮，0表示通路，1表示障礙:"<<endl; for(i=0;i<m;i+) for(j=0;j<n;j+)cin>>mazeij; void automatic_maze(int m,int n) /自動(dòng)生成迷宮int i,j;cout<<"n迷宮生成中nn"system("pause");for(i=0;i<m;i+)for(j=0;j<n;j+)mazeij=rand()%2; /隨機(jī)生成0、1maze00=0; /將開(kāi)始和結(jié)束位置強(qiáng)制為0，保證有可能出來(lái)迷宮ma

33、zem-1n-1=0;void data(int m,int n) /當(dāng)用戶輸入的不是規(guī)整的m行n列的迷宮，用來(lái)生成規(guī)則的數(shù)字迷宮int i,j; cout<<endl;cout<<"根據(jù)您先前設(shè)定的迷宮范圍"<<endl;cout<<endl;cout<<" 我們將取所輸入的前"<<m*n<<"個(gè)數(shù)生成迷宮"<<endl;cout<<"n數(shù)字迷宮生成結(jié)果如下:nn"cout<<"迷宮入

34、口n" cout<<""for(i=0;i<m;i+) cout<<"n"for(j=0;j<n;j+) if(mazeij=0) cout<<" 0"if(mazeij=1) cout<<" 1" cout<<"迷宮出口n"void print_maze(int m,int n) /打印迷宮外殼int i,j,k;cout<<"n字符迷宮生成結(jié)果如下:nn"cout<<

35、"迷宮入口n"cout<<" "cout<<endl;cout<<" " /生成上外殼for(k=0;k<n;k+)cout<<"" /這兩個(gè)黑三角用來(lái)生成頂部外殼for(i=0;i<m;i+)cout<<"n" /生成左外殼cout<<""for(j=0;j<n;j+) if(mazeij=0) printf("");if(mazeij=1) printf(&quo

36、t;");cout<<"" /生成右外殼cout<<endl;for(k=0;k<n;k+)cout<<""cout<<" n" /生成底部外殼 for(i=0;i<n;i+)cout<<" " cout<<"n"for(i=0;i<n;i+)cout<<" "cout<<"迷宮出口n"void result_maze(int m,i

37、nt n) /這個(gè)是打印輸出迷宮的星號(hào)路徑 int i,j;cout<<"迷宮通路(用表示)如下所示：nt"for(i=0;i<m;i+)cout<<"n"for(j=0;j<n;j+)if(mazeij=0|mazeij=2) /2是隊(duì)列中訪問(wèn)過(guò)的點(diǎn) cout<<""if(mazeij=1) cout<<""if(mazeij=3) /3是標(biāo)記的可以走通的路徑cout<<""void enqueue(struct poin

38、t p) /迷宮中隊(duì)列入隊(duì)操作queuetail=p;tail+; /先用再加，隊(duì)列尾部加1struct point dequeue() /迷宮中隊(duì)列出隊(duì)操作，不需要形參，因此用結(jié)構(gòu)體定義head+;return queuehead-1;int is_empty() /判斷隊(duì)列是否為空return head=tail;void visit(int row,int col,int maze5151) /訪問(wèn)迷宮矩陣中的節(jié)點(diǎn)struct point visit_point=row,col,head-1; /head-1的作用是正在訪問(wèn)的這個(gè)點(diǎn)的序號(hào)為之前的點(diǎn)序號(hào)mazerowcol=2; /將訪問(wèn)

39、過(guò)的點(diǎn)位標(biāo)記為2enqueue(visit_point);/入隊(duì)int path(int maze5151,int m,int n) /路徑求解X=1; /初始值定為1struct point p=0,0,-1; /定義入口節(jié)點(diǎn)if(mazep.rowp.col=1) /入口為1時(shí)，迷宮不可解 cout<<"n=n" cout<<"此迷宮無(wú)解nn" X=0; return 0; mazep.rowp.col=2; /標(biāo)記為已訪問(wèn) enqueue(p); /將p入隊(duì)列while(!is_empty() p=dequeue(); if

40、(p.row=m-1)&&(p.col=n-1) /當(dāng)行和列為出口時(shí)跳出 break; /定義8個(gè)走位方向 if(p.row-1)>=0)&&(p.row-1)<m)&&(p.col+0)<n)&&(mazep.row-1p.col+0=0) visit(p.row-1,p.col+0,maze); /北 if(p.row-1)>=0)&&(p.row-1)<m)&&(p.col+1)<n)&&(mazep.row-1p.col+1=0) visi

41、t(p.row-1,p.col+1,maze); /東北 if(p.row+0)<m)&&(p.col+1)<n)&&(mazep.row+0p.col+1=0) visit(p.row+0,p.col+1,maze); /東 if(p.row+1)<m)&&(p.col+1)<n)&&(mazep.row+1p.col+1=0) visit(p.row+1,p.col+1,maze); /東南 if(p.row+1)<m)&&(p.col+0)<n)&&(maz

42、ep.row+1p.col+0=0) visit(p.row+1,p.col+0,maze); /南 if(p.row+1)<m)&&(p.col-1)<n)&&(p.col-1)>=0)&&(mazep.row+1p.col-1=0) visit(p.row+1,p.col-1,maze); /西南 if(p.row+0)<m)&&(p.col-1)<n)&&(p.col-1)>=0)&&(mazep.row+0p.col-1=0) visit(p.row+0,

43、p.col-1,maze); /西 if(p.row-1)>=0)&&(p.row-1)<m)&&(p.col-1)<n)&&(p.col-1)>=0)&&(mazep.row-1p.col-1=0) visit(p.row-1,p.col-1,maze); /西北if(p.row=m-1&&p.col=n-1) /如果當(dāng)前矩陣點(diǎn)是出口點(diǎn)，輸出路徑cout<<"n=n" cout<<"迷宮路徑為：n" cout<<&

44、quot;出口"<<endl; cout<<" "<<""<<endl; printf("(%d,%d)n",p.row+1,p.col+1); cout<<" "<<""<<endl; mazep.rowp.col=3; /逆序?qū)⒙窂綐?biāo)記為3 while(p.predecessor!=-1) p=queuep.predecessor; printf("(%d,%d)n",p.row+1,p.col+1); cout<<" "<<""<<endl; mazep.rowp.col=3; cout<<"入口"<<endl;else cout<<"n=n" cout<<"此迷宮無(wú)解！nn" X=0;return 0;void main() int i,m,n,cycle=0; while(cycle!=(-1) cout<<"*n" cout<