說(shuō)在前面
“走迷宮”是一個(gè)經(jīng)典的算法問(wèn)題：給定二維地圖、入口和出口坐標(biāo)，查找行走路徑（或最短路徑）。常見思路是使用深搜或廣搜算法來(lái)尋找路徑。
浙教版《信息技術(shù)選擇性必修1數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)》5.2.2 遞歸中有一個(gè)“實(shí)踐與體驗(yàn)”，項(xiàng)目名稱是“走迷宮”，給定二維地圖、入口和出口坐標(biāo)，要求編程判斷是否能從出口走出，即判斷入口和出口是否連通。
相比輸出路徑，本題的難度降低了。教材程序采用簡(jiǎn)單的遞歸算法解決了該問(wèn)題，思路清晰、代碼簡(jiǎn)潔，對(duì)于鞏固學(xué)生對(duì)遞歸算法的理解很有幫助。教師在教學(xué)中可以引導(dǎo)學(xué)生理解教材程序中各語(yǔ)句和變量的含義，分析程序輸出兩行“successful!”的原因，并思考如何對(duì)代碼加以改進(jìn)，如何使用非遞歸算法來(lái)解決此問(wèn)題。
教材文本
教材處理
教材給出了“走迷宮”案例的實(shí)踐步驟，并提供了完整源代碼和測(cè)試數(shù)據(jù)示意圖。教師除了引導(dǎo)學(xué)生分析示意圖，理解算法思想，還應(yīng)該結(jié)合代碼，幫助學(xué)生分析程序是如何實(shí)現(xiàn)算法思想的，是否有其他的算法設(shè)計(jì)和代碼實(shí)現(xiàn)方式。
總體來(lái)說(shuō)，書中程序算法邏輯清晰，代碼簡(jiǎn)潔明了，值得學(xué)生認(rèn)真體會(huì)。同時(shí)，教師可以趁熱打鐵，在例題的基礎(chǔ)上做進(jìn)一步拓展，引導(dǎo)學(xué)生分析例題代碼的不足之處，思考改進(jìn)方法，并回顧之前學(xué)習(xí)過(guò)的棧和隊(duì)列，思考解決“走迷宮”問(wèn)題的非遞歸算法。
學(xué)生任務(wù)單
閱讀教材P125實(shí)踐與體驗(yàn)“走迷宮”，思考如下問(wèn)題：（1）書中程序使用二維數(shù)組maze存儲(chǔ)迷宮圖案，則len(maze)和len(maze[0])分別表示什么？（2）二維數(shù)組maze是用橫軸坐標(biāo)還是行列坐標(biāo)來(lái)描述元素位置的？遞歸函數(shù)walk的形式參數(shù)x和y分別表示什么？（3）maze[x][y]表示什么？當(dāng)其取值為0、1、2時(shí)分別有何含義？（4）遞歸函數(shù)walk的遞歸出口和遞歸體分別怎么表示？ （5）運(yùn)行書中程序后，輸出了兩行“successful!”，這是為什么？另外，當(dāng)入口與出口不連通時(shí)，書中程序不會(huì)輸出任何結(jié)果，你能否對(duì)程序加以改進(jìn)，使其在找到出口時(shí)只輸出一行“successful!”，并在找不到出口時(shí)，輸出“failed!”。（6）如下程序能實(shí)現(xiàn)問(wèn)題（5）的功能，試比較其與教材程序的異同，并做進(jìn)一步簡(jiǎn)化。 return 0 <= r < len(maze) and 0 <= c < len(maze[0]) and maze[r][c] == 1 #如果位置是迷宮的出口，說(shuō)明成功走出迷宮 maze[r][c] = 2 #做標(biāo)記，防止折回 #依次向上左下右四個(gè)方向試探，若找到出口，則結(jié)束查找 return False # 未找到迷宮出口，返回False（7）計(jì)算機(jī)在執(zhí)行遞歸程序時(shí)，是通過(guò)棧的調(diào)用來(lái)實(shí)現(xiàn)的。遞歸程序是將復(fù)雜問(wèn)題分解為一系列簡(jiǎn)單的問(wèn)題，從要解的問(wèn)題起，逐步分解，并將每步分解得到的問(wèn)題放入“?！敝?，運(yùn)用棧的“后進(jìn)先出”的性質(zhì)，這樣棧頂是最后分解得到的最簡(jiǎn)單的問(wèn)題，解決了這個(gè)問(wèn)題后，次簡(jiǎn)單的問(wèn)題可以得到答案，以此類推。所以，分解問(wèn)題可以看作是進(jìn)棧的過(guò)程，而解決問(wèn)題則是出棧的過(guò)程。我們可以根據(jù)這個(gè)原理，通過(guò)構(gòu)造一個(gè)棧，采用非遞歸算法來(lái)解決走迷宮問(wèn)題，參考代碼如下（僅對(duì)walk函數(shù)做了修改，其他代碼不變），請(qǐng)將缺失的代碼補(bǔ)充完整。
st = [] #用來(lái)記錄路徑點(diǎn)坐標(biāo)和朝向的棧 #分別向上左下右移動(dòng)的行列坐標(biāo)變換情況 dirs = [[-1, 0],[0, -1],[1, 0],[0, 1]] maze[r][c] = 2 #做標(biāo)記，防止折回 st.append([r, c, 0]) #將起點(diǎn)坐標(biāo)和初始朝向均入棧 for i in range(nextd, 4): #依次檢查棧頂元素未探查方向 if nextr == 8 and nextc == 8: #若找到出口，則結(jié)束查找 maze[nextr][nextc] = 2 #做標(biāo)記，防止折回 st.append([r, c, i+1]) #原位置和其下一方向入棧 st.append(填空4) #新位置和初始朝向入棧 break #退出內(nèi)層循環(huán)，處理下一位置
return False
問(wèn)題解析
（1）len(maze)表示總的行數(shù)，len(maze[0])表示總的列數(shù)。（2）二維數(shù)組maze是用行列坐標(biāo)來(lái)描述元素位置的，參數(shù)x和y分別表示迷宮中某個(gè)位置的行、列坐標(biāo)。將參數(shù)命名為x和y不太好，因?yàn)闀?huì)讓人誤以為是平面直角坐標(biāo)系中的橫縱坐標(biāo)，最好將參數(shù)改名為r和c，表示行列坐標(biāo)。（3）maze[x][y]表示第x行第y列的坐標(biāo)點(diǎn)的值，當(dāng)其取值為0、1、2時(shí)分別表示不可通行、可通行、已查找。（4）遞歸出口：當(dāng)(x==8 and y==8)時(shí)，執(zhí)行print("successful!")，并返回True。遞歸體：當(dāng)valid(maze, x, y)為True時(shí)，先設(shè)置maze[x][y] = 2，再針對(duì)四個(gè)方向依次試探，分4次遞歸調(diào)用函數(shù)walk。
（5）程序輸出了兩行“successful!”，說(shuō)明通過(guò)2條獨(dú)立的路徑找到了出口。應(yīng)該在調(diào)用walk函數(shù)時(shí)判斷是否找到出口，若找到出口則直接返回True，停止試探下一方向。可以對(duì)walk函數(shù)加以改進(jìn)，使其在找到出口時(shí)返回True，否則返回False。然后在主函數(shù)中，根據(jù)walk函數(shù)的返回值決定輸出 “successful!”或“failed!”。
（6）walk函數(shù)的遞歸體部分采用順序結(jié)構(gòu)依次向上左下右四個(gè)方向試探，代碼有些重復(fù)，可以設(shè)置一個(gè)二維數(shù)組dirs，存儲(chǔ)分別向上左下右移動(dòng)的行列坐標(biāo)變換情況，通過(guò)循環(huán)遍歷dirs，將代碼做進(jìn)一步簡(jiǎn)化。參考代碼如下： #如果位置是迷宮的出口，說(shuō)明成功走出迷宮 maze[r][c] = 2 #做標(biāo)記，防止折回 #分別向上左下右移動(dòng)的行列坐標(biāo)變換情況 dirs = [[-1, 0],[0, -1],[1, 0],[0, 1]] #依次向上左下右四個(gè)方向試探，若找到出口，則結(jié)束查找 if walk(maze,r+d[0],c+d[1]): return False # 未找到迷宮出口，返回False（7）參考代碼如下（僅對(duì)walk函數(shù)做了修改，其他代碼不變）：def walk(maze, r, c): #用棧實(shí)現(xiàn)深度優(yōu)先搜索 #如果位置是迷宮的出口，說(shuō)明成功走出迷宮 st = [] #用來(lái)記錄路徑點(diǎn)坐標(biāo)和朝向的棧 #分別向上左下右移動(dòng)的行列坐標(biāo)變換情況 dirs = [[-1, 0],[0, -1],[1, 0],[0, 1]] maze[r][c] = 2 #做標(biāo)記，防止折回 st.append([r, c, 0]) #將起點(diǎn)坐標(biāo)和初始朝向均入棧 r, c, nextd = st.pop() #退棧，并讀取棧頂元素的坐標(biāo)和朝向 for i in range(nextd, 4): #依次檢查棧頂元素未探查方向 nextr, nextc = r+dirs[i][0], c+dirs[i][1] if nextr == 8 and nextc == 8: #若找到出口，則結(jié)束查找 if valid(maze, nextr, nextc): maze[nextr][nextc] = 2 #做標(biāo)記，防止折回 st.append([r, c, i+1]) #原位置和其下一方向入棧 st.append([nextr, nextc, 0]) #新位置和初始朝向入棧 break #退出內(nèi)層循環(huán)，處理下一位置課后作業(yè)
任務(wù)（7）通過(guò)構(gòu)造一個(gè)棧來(lái)解決走迷宮問(wèn)題的算法被稱為深度優(yōu)先搜索算法，其特點(diǎn)是先沿著一個(gè)方向不斷向前查找，直到找到終點(diǎn)或此路不通為止，若某位置不通了，則退回上一位置，換個(gè)方向繼續(xù)查找。
除此之外，還有一種被稱為廣度優(yōu)先搜索的算法，它通過(guò)構(gòu)造一個(gè)隊(duì)列來(lái)存儲(chǔ)途徑點(diǎn)的坐標(biāo)，每次查找都先把當(dāng)前位置的相鄰點(diǎn)加入隊(duì)列，直到找到終點(diǎn)或隊(duì)列為空。此種算法需要占據(jù)較多空間，但是能找到最短路徑，效率較高。參考代碼如下（僅對(duì)walk函數(shù)做了修改，其他代碼不變），請(qǐng)將缺失的代碼補(bǔ)充完整。
def walk(maze, r, c): #用隊(duì)列實(shí)現(xiàn)廣度優(yōu)先搜索
#如果位置是迷宮的出口，說(shuō)明成功走出迷宮
if r == 8 and c == 8:
return True
from queue import Queue #引入queue模塊FIFO隊(duì)列Queue
q = Queue() #用來(lái)記錄路徑點(diǎn)坐標(biāo)的隊(duì)列
#分別向上左下右移動(dòng)的行列坐標(biāo)變換情況
dirs = [[-1, 0],[0, -1],[1, 0],[0, 1]]
maze[r][c] = 2 #做標(biāo)記，防止折回
q.put([r, c]) #將入口位置入列
while not q.emptue():
r, c = q.get()
for i in range(4): #依次檢查四個(gè)方向
nextr = 填空1
nextc = 填空2
if nextr == 8 and nextc == 8: #若找到出口，則結(jié)束查找
return True
if valid(填空3):
maze[nextr][nextc] = 2 #做標(biāo)記，防止折回
q.put(填空4)
return False
需要本文word文檔、源代碼和課后思考答案的，可以加入“Python算法之旅”知識(shí)星球參與討論和下載文件，“Python算法之旅”知識(shí)星球匯集了數(shù)量眾多的同好，更多有趣的話題在這里討論，更多有用的資料在這里分享。
我們專注Python算法，感興趣就一起來(lái)！
