版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、迷宮問題 迷宮問題——王欣歆 王欣歆 20080564 20080564一.需求設(shè)計(jì): 一.需求設(shè)計(jì):以一個(gè) m*m 的方陣表示迷宮,0 和 1 分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程序,對(duì)任意設(shè)定的迷宮,求出一條從入口的通道,或得出沒有通路的結(jié)論。二.概要設(shè)計(jì): 二.概要設(shè)計(jì):存儲(chǔ)結(jié)構(gòu): 存儲(chǔ)結(jié)構(gòu):采用了數(shù)組以及結(jié)構(gòu)體來存儲(chǔ)數(shù)據(jù),在探索迷宮的過程中用到的棧,屬于順序存儲(chǔ)結(jié)構(gòu)。/*八個(gè)方向的數(shù)組表示形式*/int move[8][2
2、]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1, 0},{-1, 1}};/*用結(jié)構(gòu)體表示位置*/struct position{int x,y;};position stack[m*m+1];基本算法: 基本算法:走迷宮的過程可以模擬為一個(gè)搜索的過程:每到一處,總讓它按東、東南、南、西南、西、西北、北、東北 8 個(gè)方向順序試探下一個(gè)位置;如果某方向可以通過,并且不曾到達(dá),則前進(jìn)一步,在新位
3、置上繼續(xù)進(jìn)行搜索;如果 8 個(gè)方向都走不通或曾經(jīng)到達(dá)過,則退回一步,在原來的位置上繼續(xù)試探下一位置。每前進(jìn)或后退一步,都要進(jìn)行判斷:若前進(jìn)到了出口處,則說明找到了一條通路;若退回到了入口處,則說明不存在通路。用一個(gè)字符類型的二維數(shù)組表示迷宮,數(shù)組中每個(gè)元素取值“0” (表示通路)或“1”(表示墻壁) 。迷宮的入口點(diǎn)在位置(1,1)處,出口點(diǎn)在位置(m,m)處。設(shè)計(jì)一個(gè)模擬走迷宮的算法,為其尋找一條從入口點(diǎn)到出口點(diǎn)的通路。二維數(shù)組的第 0
4、 行、第 m+1 行、第 0 列、第 m+1 列元素全置成“1” , 表示迷宮的邊界;第 1 行第 1 列元素和第 m 行第 m 列元素置成“0” , 表示迷宮的入口和出口;其余元素值用隨機(jī)函數(shù)產(chǎn)生。假設(shè)當(dāng)前所在位置是(x,y) 。沿某個(gè)方向前進(jìn)一步,它可能到達(dá)的位置最多有 8 個(gè)。如果用二維數(shù)組 move 記錄 8 個(gè)方向上行下標(biāo)增量和列下標(biāo)增量,則沿第 i 個(gè)方向前進(jìn)一步,可能到達(dá)的新位置坐標(biāo)可利用 move 數(shù)組確定:x=x+mo
5、ve[i][0]y=y+move[i][1]從迷宮的入口位置開始,沿圖示方向順序依次進(jìn)行搜索。在搜索過程中,每前進(jìn)一步,在所到位置處做標(biāo)記“?”(表示這個(gè)位置在通路上) ,并將該位置的坐標(biāo)壓入棧中。每次后退的時(shí)候,先將當(dāng)前所在位置處的通路標(biāo)記“?”改6 7 85 14 3 2xy o/*用于記錄和輸出迷宮探路中相關(guān)符號(hào),包括 1 .*/char maze[m+2][m+2];/*用棧來存儲(chǔ)探路過程中的數(shù)據(jù)*/position stack
6、[m*m+1];int top;/*棧頂*/int i,x,y,ok;position p;/*二維數(shù)組的第 0 行、第 m+1 行、第 0 列、第 m+1 列元素全置成“1“,表示迷宮的邊界;第 1 行第 1 列元素和第 m 行第 m 列元素置成“0“,表示迷宮的入口和出口;其余元素值用隨機(jī)函數(shù)產(chǎn)生。*/srand(time(0));for(x=1;x<=m;x++)for(y=1;y<=m;y++)maze[x][y]=
7、48+rand()%2;maze[1][1]='0';maze[m][m]='0';for(x=0;x<=m+1;x++){maze[x][0]='1';maze[x][m+1]='1';}for(y=0;y<=m+1;y++){maze[0][y]='1';maze[m+1][y]='1';}p.x=1;p.y=1;top=1;
8、stack[top]=p;maze[1][1]='.';/*開始探路走迷宮的過程可以模擬為一個(gè)搜索的過程:每到一處,總讓它按東、東南、南、西南、西、西北、北、東北個(gè)方向順序試探下一個(gè)位置;如果某方向可以通過,并且不曾到達(dá),則前進(jìn)一步,在新位置上繼續(xù)進(jìn)行搜索;如果個(gè)方向都走不通或曾經(jīng)到達(dá)過,則退回一步,在原來的位置上繼續(xù)試探下一位置。每前進(jìn)或后退一步,都要進(jìn)行判斷:若前進(jìn)到了出口處,則說明找到了一條通路;若退回到了入口處,
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告----迷宮問題
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告---迷宮問題
- 迷宮問題——數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)迷宮問題
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(迷宮問題)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)迷宮問題
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--迷宮問題
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-迷宮問題
- 數(shù)據(jù)結(jié)構(gòu)迷宮問題課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)—迷宮問題
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---迷宮問題
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---迷宮問題
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告--迷宮
- 數(shù)據(jù)結(jié)構(gòu)迷宮課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)迷宮課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---迷宮
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告---迷宮求解
- 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告迷宮求解
- 數(shù)據(jù)結(jié)構(gòu)迷宮求解課程設(shè)計(jì)報(bào)告
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--求解迷宮問題
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---迷宮問題求解
評(píng)論
0/150
提交評(píng)論