1、®淵州伸吊后浦數據結構課程設計大作業20140821班題目迷宮問題專業計算機科學與技術學生姓名姚鑫學號2014082309指導教師樊艷芬完成日期2016/5/19湖州師范學院信息工程學院目錄內容摘要1,jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj設計任務與技術要求,2總體設計方案2,，數據結構和算法的設計，2程序清單3，程序測試與調試，7結論與體會10I，Ii，/、，I迷宮問題【內容摘要】在一個m行，n列的迷宮中求從入口到出口的一條簡單路徑，即在求得路徑上不能同時重復出現同一通道。迷宮可用下圖所示的方塊來表示，每個方塊或者是通道（用空白方塊表示）或者是墻（用帶

2、陰影的方塊表示）。0和1分別表示迷宮中的通道和墻。輸出時簡單路徑用表示，起點用入表示，出口用出表示，墻用表示，可走的路用表示。輸入mn,表示m行n歹U。再輸入m行n列的迷宮（用0和1組成的矩陣表示），再輸入迷宮的起點和終點，輸出迷宮（含有從起點到終點的簡單路徑）。運用了深度優先搜索和遞歸的相關知識?！娟P鍵字】深度優先搜索，遞歸AbstractLookingforasimplepathfromtheentrancetotheexitinamazeofMrowsandNcolumns,thatis,theroadcouldnotberepeatedatthesametimeinthepath.Am

3、azecanbeshownasdiamondsinthefollowingfigures.Eachdiamondiseitherroadorwall.Well,ablankdiamondshowstheroadandablackdiamondshowsthewall.Intheprogram,zerorepresentsroad,andonerepresentswall.Whenweoutput,representsroad,enterstandsforstartingpoint,outstandsforexitand''representswall.Well,'

4、9;standsforthewaythatwecanchoose.Firstweshouldtypeinmandn.Thentypeinrowsofmandcolumnsofnwhichcanberepresentedbymatrixmadeofzeroandone.Intheend,weshouldtypeinthestartingpointandexit.WehavelearnedtheinformationaboutDepthFirstSearchandrecursion.KeywordsDepthFirstSearch,recursion1、 實驗內容概述（設計任務與技術要求）以一個m

5、xn的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設計一個程序，對任意設定的迷宮，求出一條從入口到出口的通路，并把這條通路顯示出來，或得出沒有通路的結論。2、 實驗目的概述（總體設計方案）a）掌握迷宮問題的DFS（深度優先搜索）解法。b）了解和熟悉深度優先搜索的思路。c）復習和熟悉二維數組的用法。d）使用圖形來美化輸出，使得輸出一目了然。3、 解題思路的描述（數據結構和算法的設計）（1）總體思路：先輸入迷宮多少行多少列（從1存到n,0行0列以及n+1行n+1列設置為墻用1表示），再輸入迷宮的入口和出口，然后遞歸調用DFS函數（深度優先搜索）來尋找從起點到終點的路線。在搜索過程中把存迷宮的

6、二維數組中每個點分別置為：0尚未走過的路1墻2路線然后判斷是否存在這樣一條路線，如果不存在，就輸出“不存在從入口到出口的路線”；如果存在，就輸出迷宮（包括路線）。并輸出注釋。''meanstheroute''meanstheroad''meansthewall（2）數據結構的選擇和描述：選用了int類型數組，數組a用來存儲迷宮，結構體Point用來定義入口坐標和出口坐標，x代表橫坐標，y代表縱坐標。flag用來記錄dfs時是否找到出口，即退出dfs的標志。（flag為1時找到出口，為0時沒找到）（3）要算法的功能和描述：采用了深度優先搜索（DFS

7、的思想。每次搜索的方向依次為右下左上，每搜索一個點就標記為2,若從該點的四個方向進行dfs都無法找到出口，就重新標記為0.;（4）DFS的具體描述：1 .傳入一個點的橫縱坐標，一開始就把傳入的存迷宮的這個二維數組節點標記為2（路線），2 .判斷是否為終點，如果是終點flag標記為1（防止退出DFS時走過的路線被還原0）,并跳出DFS函數；否則什么也不做，繼續往下運行；3 .向右搜索：判斷右邊相鄰的結點是否違反要求（即是否是墻或者越界），如果不違反要求，就把右邊相鄰的結點傳入DFS進行搜索；否則什么也不做，繼續運行；判斷是否已經找到終點，若已經找到終點（flag=1）直接跳出函數；4 .向下搜索

8、：判斷下邊相鄰的結點是否違反要求（即是否是墻或者越界），如果不違反要求，就把下邊相鄰的結點傳入DFS進行搜索；否則什么也不做，繼續運行；判斷是否已經找到終點，若已經找到終點（flag=1）直接跳出函數；5 .向左搜索：判斷左邊相鄰的結點是否違反要求（即是否是墻或者越界），如果不違反要求，就把左邊相鄰的結點傳入DFS進行搜索；否則什么也不做，繼續運行；判斷是否已經找到終點，若已經找到終點（flag=1）直接跳出函數；6 .向上搜索：判斷上邊相鄰的結點是否違反要求（即是否是墻或者越界），如果不違反要求，就把上邊相鄰的結點傳入DFS進行搜索；否則什么也不做，繼續運行；判斷是否已經找到終點，若已經找到

9、終點（flag=1）直接跳出函數；7 .運行到這里還沒找到終點表示此路不通，把這點還原為沒走過時的樣子（重新標記為0）;4、 源程序清單（源程序中應該附有必要的注釋）(1)源程序#include<stdio.h>typedefstructpointintx;inty;Point;Pointstart,end;inta4040;intm,n;intflag=0;voiddfs(intx,inty)axy=2;if(x=end.x)&&(y=end.y)flag=1;return;if(y+1<=n)&&(axy+1=0)dfs(x,y+1);if

10、(flag)/迷宮中每個點/迷宮的入口與出口/輸入時迷宮存儲的數組m:行n:歹U/signofexitdfs退出的標志/深度優先搜索/表示x行y列這個位置已被走過/找到了出口/退出dfs,防止走過的路線被還原/向右搜索return;)if(x+1<=m)&&(ax+1y=0)dfs(x+1,y);)if(flag)return;)if(y-1>=1)&&(axy-1=0)dfs(x,y-1);)if(flag)return;)if(x-1>=1)&&(ax-1y=0)dfs(x-1,y);)if(flag)return;)axy

11、=0;)/向下搜索/向左搜索/向上搜索/此路不通，把這點還原為沒走過時的樣子intmain()inti,j;printf("請輸入多少行多少列：(m,n)(注：輸入00結束)n");while(scanf("%d%d”,&m,&n)&&(m|n)/輸入00結束printf("請輸入迷宮：(1表示墻0表示路)n");for(i=0;i<=m+1;i+)/輸入迷宮for(j=0;j<=n+1;j+)if(i=0|j=0|i=m+1|j=n+1)/外面置為1,即墻a皿=1;elsescanf("%

12、d",&aij);printf("請輸入迷宮入口和出口：x1y1x2y2n");scanf("%d%d%d%d",&start.x,&start.y,&end.x,&end.y);dfs(start.x,start.y);if(!flag)printf("不存在從入口到出口的路線n");for(i=0;i<=m+1;i+)for(j=0;j<=n+1;j+)if(i=start.x&&j=start.y)printf("入");elsei

13、f(i=end.x&&j=end.y)printf("出)elseif(aij=1)printf("");elseif(aij=0)printf("");elseif(aij=2)printf("");printf("n");/printf("''meanstherouten");printf("''meanstheroadn");printf("''meansthewalln");

14、return0;/輸入迷宮入口及出口/深度優先搜索搜索路徑/輸出結果/入口輸出美化出口輸出美化/墻輸出美化/路輸出美化/路線輸出美化換行/注釋(2) 算法的時間復雜度是什么？算法的空間復雜度是什么？為什么?答：空間復雜度：線性時間復雜度，具體看最長的那條路徑長度。棧中維持單一路徑上的節點;時間復雜度：O(m+1)*(n+1)注：存儲迷宮所用的行數乘列數;(3) 還可以擴充自己的想法，題目要求所編程序都能適用哪些情況，如果做一些修改，還能適合什么情況(能解決什么問題)？答：此代碼還可以解決類似的尋找路徑問題，且輸出形象簡潔。做一些修改可以解決大多數的DFS問題，如油田問題(記憶化搜索)；(4)

15、說明在這個程序中所使用的各變量、形式參數的具體含義及各子程序之間的調用關系等。答：1. 調用關系：調用DFS函數，且在搜索的過程中一直調用，直到找到終點。2. 結構體Point:用來表示迷宮的每個結點，擁有成員變量x,y皆為整形。3. Start,End:a) Start:迷宮的起點；b) End:迷宮的終點4. a4040:存儲迷宮的數組；5. m,n：a) m行；b) n歹U;6. flag:dfs退出的標志；五、程序調試及測試結果（1） 上機調試上述程序，總結在調試過程中出現的問題及解決方法1 .一開始沒有定義flag導致找到從起點到終點的路線后無法輸出路線。因為在退出時都被還原了（還原

16、為未走過時的樣子了）；2 .在美化輸出時沒有考慮到有些字符是普通的一個字符的兩倍，導致輸出完全不對；3 .沒有考慮找不到從起點到終點的路線時的情況；4 .深度優先搜索時在搜索完四個方向都沒有找到終點時忘記把這個點還原為0了;（2） 給出幾組有代表性的數據，運行上述程序，查看運行結果，分析運行結果。截圖15X5的迷宮從（1,1）到（5,5）的路線tC:U5er5Administrator,Desk±op健高巨至2exe睛輸入多少行多少列:晴輸入迷宮：（工表示墻口表示路）II1010601011aiq&&情輸入迷宮入口和出口工WX2皿1135懷存在從人口到出口的路線人ne

17、ansr1n&ansJ1nesnsthethetherouteroaduall截圖25X5的迷宮從（1,1）到（3,5）,不存在路線截圖3書上的例子（6X9的迷宮）從（1,1）到（6,9）的路線截圖4書上的例子（6X9的迷宮）從（1,1）到（1,9）路線截圖512X18的迷宮從（1,1）到（12,18）的路線六、結論與體會（1） 在解決和設計本文題目所涉及到的問題時，你所采取的方法、手段和關鍵性的技術。采用了DFS（深度優先搜索），遞歸，輸出的轉化。（2） 在調試程序的過程中你所遇到的問題及解決方法。1 .一開始沒有定義flag導致找到從起點到終點的路線后無法輸出路線。因為在退出時都被

18、還原了。（還原為未走過時的樣子了）；2 .在美化輸出時沒有考慮到有些字符是普通的一個字符的兩倍，導致輸出完全不對3 .沒有考慮找不到從起點到終點的路線時的情況；4 .深度優先搜索時在搜索完四個方向都沒有找到終點時忘記把這個點還原為0了;（3） 關于程序的特色和改進設想。特色：1 .輸出十分形象簡潔，只要輸入迷宮以及起點終點就可以輸出所求路線（路線存在的情況下）2 .采用了深度優先搜索，代碼簡潔，可讀性高；3 .深度優先搜索時的改變方向的方式采用了最簡單，易懂的方式，雖然啰嗦，但是可讀性好；改進設想：1.可以使用BFS（廣度優先搜索），可以找出從起點到終點的最短路徑，但是代碼會變得更長，用到了隊列，可讀性降低。2.使用C+的容器隊列來使用BFS,可是代碼簡潔。（4）其他需要說明的情況。任意大小的迷宮以及任意的起點與終點皆可計算出從起點到終點的路徑（雖然不是最短的）。結：迷宮問題我一開始在輸出的處理上有點問題，我一開始把存迷宮的int型二維數組轉存到char的字符型