《迷宮問題大作業(yè)(共13頁).doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《迷宮問題大作業(yè)(共13頁).doc（13頁珍藏版）》請(qǐng)?jiān)趨R文網(wǎng)上搜索。

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

2、示，出口用出表示，墻用表示，可走的路用 表示。 輸入m，n,表示m行n列。再輸入m行n列的迷宮（用0和1組成的矩陣表示），再輸入迷宮的起點(diǎn)和終點(diǎn)，輸出迷宮（含有從起點(diǎn)到終點(diǎn)的簡(jiǎn)單路徑）。運(yùn)用了深度優(yōu)先搜索和遞歸的相關(guān)知識(shí)?！娟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 m

3、aze 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 s

4、tands 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

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

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

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

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

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

10、t,end; /迷宮的入口與出口 int a4040; /輸入時(shí)迷宮存儲(chǔ)的數(shù)組 int m,n; /m:行 n:列 int flag=0; / sign of exit dfs退出的標(biāo)志 void dfs(int x, int y) /深度優(yōu)先搜索 axy=2;/表示x行y列這個(gè)位置已被走過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)&&a

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

12、&n)&&(m|n)/輸入0 0 結(jié)束 printf("請(qǐng)輸入迷宮：（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("請(qǐng)輸入迷宮入口和出口: x1 y1 x2 y2n");scanf("%d%d%d%d",&start.x,&start.y,&end.

13、x,&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("");els