迷宮問題大作業(yè)

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計大作業(yè)20140821班題 目 迷宮問題 專 業(yè) 計算機科學(xué)與技術(shù) 學(xué)生姓名 姚鑫 學(xué) 號 2014082309 指導(dǎo)教師 樊艷芬 完成日期 2016/5/19 湖州師范學(xué)院信息工程學(xué)院目 錄內(nèi)容摘要1設(shè)計任務(wù)與技術(shù)要求 2總體設(shè)計方案2數(shù)據(jù)結(jié)構(gòu)和算法的設(shè)計2程序清單3程序測試與調(diào)試7結(jié)論與體會10迷宮問題【內(nèi)容摘要】在一個m行，n列的迷宮中求從入口到出口的一條簡單路徑，即在求得路徑上不能同時重復(fù)出現(xiàn)同一通道。迷宮可用下圖所示的方塊來表示，每個方塊或者是通道(用空白方塊表示)或者是墻(用帶陰影的方塊表示)。0和1分別表示迷宮中的通道和墻。輸出時簡單路徑用表示，起點用入表示，出口

2、用出表示，墻用表示，可走的路用 表示。 輸入m，n,表示m行n列。再輸入m行n列的迷宮（用0和1組成的矩陣表示），再輸入迷宮的起點和終點，輸出迷宮（含有從起點到終點的簡單路徑）。運用了深度優(yōu)先搜索和遞歸的相關(guān)知識?！娟P(guān)鍵字】深度優(yōu)先搜索 ，遞歸【Abstract】Looking for a simple path from the entrance to the exit in a maze of M rows and N columns, that is, the road could not be repeated at the same time in the path. A maze

3、can be shown as diamonds in the following figures. Each diamond is either road or wall. Well , a blank diamond shows the road and a black diamond shows the wall .In the program ,zero represents road ,and one represents wall. When we output, represents road, enter stands for starting point ,out stand

4、s for exit and represents wall. Well, stands for the way that we can choose.First we should type in m and n. Then type in rows of m and columns of n which can be represented by matrix made of zero and one. In the end, we should type in the starting point and exit.We have learned the information abou

5、t Depth First Search and recursion.【Key words】Depth First Search ，recursion一、 實驗內(nèi)容概述(設(shè)計任務(wù)與技術(shù)要求) 以一個m×n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計一個程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，并把這條通路顯示出來，或得出沒有通路的結(jié)論。二、 實驗?zāi)康母攀?總體設(shè)計方案) a) 掌握迷宮問題的DFS（深度優(yōu)先搜索）解法。b) 了解和熟悉深度優(yōu)先搜索的思路。c) 復(fù)習(xí)和熟悉二維數(shù)組的用法。d) 使用圖形來美化輸出，使得輸出一目了然。三、 解題思路的描述(數(shù)據(jù)結(jié)構(gòu)和算

6、法的設(shè)計) （1） 總體思路：先輸入迷宮多少行多少列（從1存到n，0行0列以及n+1行n+1列設(shè)置為墻用1表示），再輸入迷宮的入口和出口，然后遞歸調(diào)用DFS函數(shù)（深度優(yōu)先搜索）來尋找從起點到終點的路線。在搜索過程中把存迷宮的二維數(shù)組中每個點分別置為：0 尚未走過的路 1 墻2 路線然后判斷是否存在這樣一條路線，如果不存在，就輸出“不存在從入口到出口的路線”；如果存在，就輸出迷宮（包括路線）。并輸出注釋。'' means the route' ' means the road'' means the wall（2） 數(shù)據(jù)結(jié)構(gòu)的選擇和描述：選用了in

7、t類型數(shù)組，數(shù)組a用來存儲迷宮，結(jié)構(gòu)體Point用來定義入口坐標和出口坐標，x代表橫坐標，y代表縱坐標。flag用來記錄dfs時是否找到出口，即退出dfs的標志。（flag為1時找到出口，為0時沒找到）（3） 要算法的功能和描述：采用了深度優(yōu)先搜索（DFS）的思想。每次搜索的方向依次為 右 下 左 上，每搜索一個點就標記為2，若從該點的四個方向進行dfs都無法找到出口，就重新標記為0.；（4） DFS的具體描述：1.傳入一個點的橫縱坐標，一開始就把傳入的存迷宮的這個二維數(shù)組節(jié)點標記為2（路線），2.判斷是否為終點，如果是終點flag標記為1（防止退出DFS時走過的路線被還原0），并跳出DFS函

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

9、繼續(xù)運行；判斷是否已經(jīng)找到終點，若已經(jīng)找到終點（flag=1）直接跳出函數(shù)；6.向上搜索：判斷上邊相鄰的結(jié)點是否違反要求（即是否是墻或者越界），如果不違反要求，就把上邊相鄰的結(jié)點傳入DFS進行搜索；否則什么也不做，繼續(xù)運行；判斷是否已經(jīng)找到終點，若已經(jīng)找到終點（flag=1）直接跳出函數(shù)；7.運行到這里還沒找到終點表示此路不通，把這點還原為沒走過時的樣子（重新標記為0）；四、 源程序清單（源程序中應(yīng)該附有必要的注釋）（1） 源程序#include<stdio.h>typedef struct pointint x;int y;Point;/迷宮中每個點 Point start,en

10、d; /迷宮的入口與出口 int a4040; /輸入時迷宮存儲的數(shù)組 int m,n; /m:行 n:列 int flag=0; / sign of exit dfs退出的標志 void dfs(int x, int y) /深度優(yōu)先搜索 axy=2;/表示x行y列這個位置已被走過if(x=end.x)&&(y=end.y)/找到了出口 flag=1;/退出dfs，防止走過的路線被還原 return ;if(y+1<=n)&&(axy+1=0)/向右搜索 dfs(x,y+1);if(flag)return;if(x+1<=m)&&(

11、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=0;/此路不通，把這點還原為沒走過時的樣子 int main()int i,j;printf("請輸入多少行多少列：（m,n）(注：輸入0 0結(jié)束)n");while(scanf("%d%d",&m,&

12、;n)&&(m|n)/輸入0 0 結(jié)束 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，即墻 aij=1;elsescanf("%d",&aij);printf("請輸入迷宮入口和出口: x1 y1 x2 y2n");scanf("%d%d%d%d",&start.x,&start.y,&end.x,&a

13、mp;end.y);/輸入迷宮入口及出口 dfs(start.x,start.y);/深度優(yōu)先搜索 搜索路徑 if(!flag)printf("不存在從入口到出口的路線n");for(i=0;i<=m+1;i+) /輸出結(jié)果for(j=0;j<=n+1;j+)if(i=start.x&&j=start.y)/入口 輸出美化printf("入");else if(i=end.x&&j=end.y)/出口 輸出美化printf("出");else if(aij=1)/墻 輸出美化printf(&

14、quot;");else if(aij=0)/路 輸出美化printf(" ");else if(aij=2)/路線 輸出美化printf("");printf("n"); /換行 printf("'' means the routen"); /注釋 printf("' ' means the roadn");printf("'' means the walln");return 0;（2） 算法的時間復(fù)雜度是什么？算

15、法的空間復(fù)雜度是什么？為什么？答：空間復(fù)雜度：線性時間復(fù)雜度，具體看最長的那條路徑長度。棧中維持單一路徑上的節(jié)點；時間復(fù)雜度：O（(m+1 )*(n+1)） 注：存儲迷宮所用的行數(shù)乘列數(shù)；（3） 還可以擴充自己的想法，題目要求所編程序都能適用哪些情況，如果做一些修改，還能適合什么情況（能解決什么問題）？答：此代碼還可以解決類似的尋找路徑問題，且輸出形象簡潔。做一些修改可以解決大多數(shù)的DFS問題，如油田問題（記憶化搜索）；（4） 說明在這個程序中所使用的各變量、形式參數(shù)的具體含義及各子程序之間的調(diào)用關(guān)系等。答：1. 調(diào)用關(guān)系：調(diào)用DFS函數(shù)，且在搜索的過程中一直調(diào)用，直到找到終點。2. 結(jié)構(gòu)體P

16、oint:用來表示迷宮的每個結(jié)點，擁有成員變量x,y皆為整形。3. Start ，End：a) Start：迷宮的起點；b) End: 迷宮的終點4. a4040：存儲迷宮的數(shù)組；5. m,n：a) m 行;b) n 列;6. flag: dfs退出的標志;五、 程序調(diào)試及測試結(jié)果（1） 上機調(diào)試上述程序，總結(jié)在調(diào)試過程中出現(xiàn)的問題及解決方法1. 一開始沒有定義flag導(dǎo)致找到從起點到終點的路線后無法輸出路線。因為在退出時都被還原了（還原為未走過時的樣子了）；2. 在美化輸出時沒有考慮到有些字符是普通的一個字符的兩倍，導(dǎo)致輸出完全不對；3. 沒有考慮找不到從起點到終點的路線時的情況；4. 深度

17、優(yōu)先搜索時在搜索完四個方向都沒有找到終點時忘記把這個點還原為0了； （2） 給出幾組有代表性的數(shù)據(jù)，運行上述程序，查看運行結(jié)果，分析運行結(jié)果。截圖 1 5×5的迷宮從（1，1）到（5，5）的路線截圖 2 5×5的迷宮從（1，1）到（3，5），不存在路線截圖 3 書上的例子（6×9的迷宮）從（1，1）到（6，9）的路線截圖 4 書上的例子（6×9的迷宮）從（1，1）到（1，9）路線截圖 5 12×18的迷宮從（1，1）到（12，18）的路線六、 結(jié)論與體會（1） 在解決和設(shè)計本文題目所涉及到的問題時，你所采取的方法、手段和關(guān)鍵性的技術(shù)。采用了DF

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