迷宮問題的關(guān)鍵操作要點(diǎn)

姓名設(shè)計題目：迷宮問題的操作設(shè)計任務(wù)(重要技術(shù)參數(shù)):學(xué)會運(yùn)用數(shù)據(jù)構(gòu)造建立迷宮問題，編造出迷宮并設(shè)計出走出迷宮的措施硬件環(huán)境：處理器：英特爾第三代酷睿i3-3GHz內(nèi)存：4GB(三星DDR31333MHz)主硬盤：希捷ST500LM012HN-M500MBB(500GB/5400轉(zhuǎn)/分)顯示屏：三星SEC3649(14英寸)軟件環(huán)境：操作系統(tǒng)：Windows864位(DirectX11)指導(dǎo)教師評語：1、課程設(shè)計目的構(gòu)造的應(yīng)用、算法的編寫、類C語言的算法轉(zhuǎn)換成C程序并用TC上機(jī)調(diào)試的基本據(jù)構(gòu)造中鏈表的創(chuàng)立、合并等措施以和怎樣通過轉(zhuǎn)化成C語言在微機(jī)上運(yùn)行實現(xiàn)等其他方面的能力。2.1問題描述：迷宮問題是取自心理學(xué)的一種古典試驗。在該試驗中，把一只老鼠從一種無頂大盒子的門放入，在盒子中設(shè)置了許多墻，對行進(jìn)方向形成了多處阻擋。盒子僅有一種出口，在出口處放置一塊奶酪，吸引老鼠在迷宮中尋找道路以抵達(dá)出口。對同一只老鼠反復(fù)進(jìn)行上述試驗，一直到老鼠從入口走到出口，而不走錯一步。老鼠通過多次試驗最終學(xué)會走通迷宮的路線。設(shè)計一種計算機(jī)程序?qū)θ我庠O(shè)定的矩形迷宮如下圖A所示，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。????????(3)用一種標(biāo)志(如數(shù)字8)在迷宮中標(biāo)出該條通路；3.課程設(shè)計總體方案和分析3.迷宮途徑的搜索：首先從迷宮的入口開始，假如該位置就是迷宮出口，則已經(jīng)找到了一條途徑，搜索工作結(jié)束。否則搜索其上、下、左、右位置與否是障礙，若不是障礙，就移動到該位置，然后再從該位置開始搜索通往出口的途徑；若是障礙就選擇另一種相鄰的位置，并從它開始搜索途徑。為防止搜索反復(fù)出現(xiàn)，則將已搜索過的位置標(biāo)識為2,同步保留搜索痕跡，在考慮進(jìn)入下一種位置搜索之前，將目前位置保留在一種隊列中，假如所有相鄰的非障礙位置均被搜索過，且未找到通往出口的途徑，則表明不存在從入口到出口的途徑。這實現(xiàn)的是廣度優(yōu)先遍歷的算法，假如找到途徑，則為最短途徑。以矩陣00101為例，來示范一下首先，將位置(0,0)(序號0)放入隊列中，其前節(jié)點(diǎn)為空，從它開始搜索，其標(biāo)識變?yōu)?,由于其只有一種非障礙位置，因此接下來移動到(0,1)(序號1),其前節(jié)點(diǎn)序號為0,標(biāo)識變?yōu)?,然后從(0,1)移動到(1,1)(序號2),放入隊列中，其前節(jié)點(diǎn)序號為1,(1,1)存在(1,2)(序號3)、(2,1)(序號4)兩個可移動位置，其前節(jié)點(diǎn)序號均為2.對于每一種非障礙位置，它的相鄰非障礙節(jié)點(diǎn)均入隊列，且它們的前節(jié)點(diǎn)序號均為該位置的序號，因此假如存在途徑，則從出口處節(jié)點(diǎn)的位置，逆序就可以找到其從出口到入口的通路。如下表所示：由此可以看出，得到最短途徑：(3,4)(3,3)(2,3)(2,2)(1,2)(1,1)(0,1)(0,0)搜索算法流程圖如下所示：將(0,0)入隊列YNN是杏到達(dá)迷宮處Y右邊是否存在下邊是否存在是否存在是否存在N1.①構(gòu)建一種二維數(shù)組maze[M+2][N+2]用于存儲迷宮矩陣②自動或手動生成迷宮，即為二維數(shù)組maze[M+2][N+2]賦值③構(gòu)建一種隊列用于存儲迷宮途徑④建立迷宮節(jié)點(diǎn)structpoint,用于存儲迷宮中每個節(jié)點(diǎn)的訪問狀況⑤實現(xiàn)搜索算法⑥屏幕上顯示操作菜單2.迷宮的操作{定義ij為循環(huán)變量{定義ij為循環(huán)變量②迷宮中隊列出隊操作③判斷隊列與否為空{(diào)返回head==tail的值，當(dāng)隊列為空時，返回0}④訪問迷宮矩陣中節(jié)點(diǎn)voidvisitintrowintcolint⑤途徑求解voidmgpath(intmaze[intmintn為障礙，則此迷宮無解，返回0,程序結(jié)束。否則訪問入口節(jié)點(diǎn)，將入口節(jié)點(diǎn)判斷隊列與否為空，當(dāng)隊列不為空時，則運(yùn)行如下操作：{調(diào)用dequeue()函數(shù)，將隊頭元素返回給p,假如p.row==m-1且p.col==n-1,即抵達(dá)出口節(jié)點(diǎn)，即找到了途徑，結(jié)束假如p.col+1<n且maze[p.row][p.col+1]==0,闡明訪問到出口(找到途徑)即p.row==m-1且p.col==n-1,則逆序?qū)⑼緩綐?biāo)識為3即最終將途徑圖形打印出來。3.菜單項選擇擇☆手動生成迷宮請按：1☆自動生成迷宮請按：2☆退出請按：3{case1:請輸入行列數(shù)(假如超過預(yù)設(shè)范圍則提醒重新輸入)}在調(diào)試過程中，首先使用的是棧進(jìn)行存儲，不過C:\DocmentsandSettings\nev\桌面\Dcbug\Cpp1.exe'歡迎進(jìn)入迷宮求解系統(tǒng)NNKFKNKNNSNNSNNCNNNNKNSNNCKKNNNNSSFNNSNSNNSSRNNNNNSNNN舌動生盛類宴請接：小請選擇你的操作：1請輸入行數(shù)：44請輸入列數(shù)：4抱歉，你輸入的行列數(shù)超出預(yù)設(shè)范圍<8-39,8-39>,請重新輸入：請輸入行數(shù)：4請輸入列數(shù)：4請按行輸入迷宮，B表示通路，1表示障礙：迷宮生成結(jié)果如下：迷宮入口請輸入行數(shù)：44迷宮生成結(jié)果如下迷喜入口…迷宮路徑為：(3.3)(1.0)(0.0)迷言通路(用☆表示)如下所示：搜狗拼音輸入法全：KK歡迎進(jìn)入迷宮求解系統(tǒng)☆☆手動生成迷言請按：1☆自動生成據(jù)言請按：2☆退出請按：3xkm**xxxmkx?0*xxmk***mxxxmxkmb?xxmm**m**xmxxxk*2請按任意健繼續(xù)...北選宮無解搜物拼音輸入法全：通過本次的課程設(shè)計，使我學(xué)會了怎樣去組織代碼量較大大程序。與此同步，也使我學(xué)會了某些對代碼量較大的的程序進(jìn)行編寫、連接、編譯運(yùn)行、以和調(diào)試和修改的技巧這次的課程設(shè)計涉和到編程語言和數(shù)據(jù)構(gòu)造的知識，規(guī)定和平時的實比相對較高。從本次的課程設(shè)計可以檢查我們對C語言和數(shù)據(jù)構(gòu)造的掌握狀況，同步也檢查了我們對所學(xué)習(xí)過的知識的靈活運(yùn)用狀況。在創(chuàng)新性方面，這次的課程設(shè)計雖然完畢了課程設(shè)計的任務(wù)，不過缺乏發(fā)明性的設(shè)計思想，在后來的學(xué)習(xí)過程中還得繼續(xù)努力。[1].嚴(yán)蔚敏編著.數(shù)據(jù)構(gòu)造(C語言版).清華大學(xué)出版社，2023[2].朱戰(zhàn)立.編著.數(shù)據(jù)構(gòu)造——使用C語言.西安交通大學(xué)出版社，2023[4].蘇小紅，孫志崗等編著.C語言大學(xué)實用教程(第2版).電子工業(yè)出版社，})if(maze[i][j]=printf}}if(maze[i][j]=printf)))}}}}}{printf('\n=====================}{printf('\n========================)print(***************************************************************rint***********************************************