C語(yǔ)言課件 第21 22章

1、第21章迷宮求解p 問(wèn)題描述 p 問(wèn)題分析及實(shí)現(xiàn) p 開(kāi)發(fā)過(guò)程常見(jiàn)問(wèn)題及解決第21章迷宮求解 問(wèn)題描述 p 問(wèn)題分析及實(shí)現(xiàn) p 開(kāi)發(fā)過(guò)程常見(jiàn)問(wèn)題及解決第21章迷宮求解 問(wèn)題描述 問(wèn)題分析及實(shí)現(xiàn) p 開(kāi)發(fā)過(guò)程常見(jiàn)問(wèn)題及解決第21章迷宮求解 問(wèn)題描述 問(wèn)題分析及實(shí)現(xiàn) 開(kāi)發(fā)過(guò)程常見(jiàn)問(wèn)題及解決迷宮求解 c語(yǔ)言的功能是強(qiáng)大的，可以實(shí)現(xiàn)很多有意義的問(wèn)題的求解。比如算法領(lǐng)域的經(jīng)典問(wèn)題迷宮求解。在一個(gè)mn的迷宮中，給定一個(gè)入口，一個(gè)出口，如何從入口走到出口？本章就實(shí)現(xiàn)了這一算法。21.1 問(wèn)題描述 以一個(gè)mn的長(zhǎng)方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通路并輸出

2、所經(jīng)過(guò)的坐標(biāo)點(diǎn)，或得出沒(méi)有通路的結(jié)論。21.2 問(wèn)題分析及實(shí)現(xiàn) 21.2.1 問(wèn)題分析 21.2.2 問(wèn)題實(shí)現(xiàn) 21.2.3 程序運(yùn)行21.2 問(wèn)題分析及實(shí)現(xiàn) 由問(wèn)題描述可知，我們要實(shí)現(xiàn)的是打印從坐標(biāo)a，走到坐標(biāo)b，要繞過(guò)路障走一條路徑出來(lái)。簡(jiǎn)單舉例：從左向右走動(dòng)，中間有障礙物，此時(shí)，需要向上再向右，或向下再向右，只有繞過(guò)左與右之間的障礙物，才可以順利從左走至右，以下將仔細(xì)地分析問(wèn)題并實(shí)現(xiàn)算法。21.2.1 問(wèn)題分析 我們的將要開(kāi)發(fā)的程序，就是設(shè)置一個(gè)迷宮（mn）,并設(shè)置入口點(diǎn)，出口點(diǎn)，從出口點(diǎn)走向入口點(diǎn)，將途經(jīng)的坐標(biāo)記錄到“?！钡祝谡业铰窂綍r(shí)，將彈出棧頂元素，此時(shí)，就是所有途經(jīng)的坐標(biāo)點(diǎn)。2

3、1.2.2 問(wèn)題實(shí)現(xiàn) 本小節(jié)就來(lái)通過(guò)編程求解迷宮問(wèn)題，實(shí)現(xiàn)的代碼如下。 1. 采用結(jié)構(gòu)體保存過(guò)程數(shù)據(jù) 通過(guò)定義兩個(gè)結(jié)構(gòu)體類型，分別記錄棧中的走過(guò)的坐標(biāo)及走過(guò)的方向，采用結(jié)構(gòu)體實(shí)現(xiàn)棧的存儲(chǔ)。那么，根據(jù)這個(gè)思路，代碼如下（代碼21-1.txt）。nnn21.2.2 問(wèn)題實(shí)現(xiàn) 2. 輸出結(jié)果 將結(jié)果輸出至屏幕，以循環(huán)打印的方式，調(diào)用標(biāo)準(zhǔn)輸入輸出函數(shù)printf,將結(jié)果回顯。代碼如下（代碼21-2.txt）。21.2.2 問(wèn)題實(shí)現(xiàn)01 /*輸出路徑*/02 void outputpath(pseqstack st) 03 04 datatype element; 05 printf(nn出迷宮的路徑是

4、:n); 06 while(!isemptystack_seq(st) 07 08 element = top_seq(st); 09 pop_seq(st); 10 printf(n路過(guò)的節(jié)點(diǎn)坐標(biāo)是: 第%d行 第%d列, element.x, element.y);/* 打印路徑上的每一點(diǎn)*/11 12 21.2.2 問(wèn)題實(shí)現(xiàn) 3. 求解經(jīng)過(guò)的坐標(biāo)點(diǎn)及方向 從入口點(diǎn)開(kāi)始，依次試探四個(gè)方向，只要某個(gè)方向沒(méi)有障礙，則繼續(xù)這個(gè)方向，并將這個(gè)方向不是障礙物的點(diǎn)做為下一個(gè)當(dāng)前點(diǎn)，循環(huán)直到到達(dá)入口點(diǎn)。代碼如下（代碼21-3.txt）21.2.3 程序運(yùn)行 單擊【調(diào)試】工具欄中的按鈕，即可輸出以下運(yùn)行結(jié)果。21.3 開(kāi)發(fā)過(guò)程常見(jiàn)問(wèn)題及解決 開(kāi)發(fā)過(guò)程常見(jiàn)問(wèn)題及解決辦法如下，僅供參考。 在程序中，如何表示一個(gè)坐標(biāo)點(diǎn)呢？方法很簡(jiǎn)單：只需要用一對(duì)變量即可保存。即：一個(gè)變量保存橫坐標(biāo)，另外一個(gè)變量保存縱坐