全國青少年信息學(xué)奧林匹克競賽NOI信息學(xué)-遞歸與深度優(yōu)先搜索DFSPowerPoint 演示文稿

1、1遞歸與深度優(yōu)先搜索遞歸與深度優(yōu)先搜索2迷宮求解迷宮求解31、迷宮求解、迷宮求解-定義數(shù)據(jù)結(jié)構(gòu)，讀取迷宮信息定義數(shù)據(jù)結(jié)構(gòu)，讀取迷宮信息 從題意和樣例數(shù)據(jù)可以看出，迷宮中每個方格的行下標(biāo)和列下標(biāo)，都是從1開始編號的。 為了便于處理，我們也可以將數(shù)組預(yù)留一部分空間，數(shù)組行下標(biāo)和列下標(biāo)也從1開始編號l mapij取值為0，表示可以通過；取值為1，表示有障礙，不可通過l 因為數(shù)組的行下標(biāo)和列下標(biāo)都從1開始，且1=N、M(1, 2)-(1, 1).的重復(fù)遞歸調(diào)用，導(dǎo)致程序死循環(huán)，函數(shù)無法退出00001010063、迷宮求解、迷宮求解-定義數(shù)組標(biāo)記方格已經(jīng)被訪問（定義數(shù)組標(biāo)記方格已經(jīng)被訪問（解決死循環(huán)解決

2、死循環(huán)）7練習(xí)練習(xí)8洛谷洛谷P1238(走迷宮、求迷宮的所有路徑走迷宮、求迷宮的所有路徑)91、洛谷、洛谷P1238(走迷宮、求迷宮的所有路徑走迷宮、求迷宮的所有路徑)-解題思路解題思路該題的解題思路與上題類似以起始點為參照，尋找上、下、左、右可到達(dá)的方格將上、下、左、右可到達(dá)的方格設(shè)為新的起始點1.回到步驟1。直到?jīng)]有可到達(dá)的方格或者到達(dá)終點為止100011101011101101110111110DFS搜索樹與回溯搜索樹與回溯 有一棵如右圖的路徑樹，假設(shè)我們尋找一條從小紅點到小綠點的路徑 在尋找路徑時，若遇到不滿足條件的組合，往回走的過程，就稱之為回溯112、洛谷、洛谷P1238(走迷宮走

3、迷宮)-編寫程序判斷是否存在從起點到達(dá)終點編寫程序判斷是否存在從起點到達(dá)終點的路徑的路徑visit數(shù)組防止重復(fù)遞歸123、洛谷、洛谷P1238(走迷宮走迷宮)-定義數(shù)組，保存求解路徑定義數(shù)組，保存求解路徑每條路徑最多經(jīng)過所有的方格134、洛谷、洛谷P1238(走迷宮走迷宮)-增加路徑展示函數(shù)增加路徑展示函數(shù)145、洛谷、洛谷P1238(走迷宮走迷宮)-重置訪問狀態(tài)，實現(xiàn)尋找過程回溯重置訪問狀態(tài)，實現(xiàn)尋找過程回溯將visit置0，實現(xiàn)路徑尋找回溯15洛谷洛谷P1141(01迷宮迷宮)題目意思：求從某一格開始可到達(dá)的格子總數(shù)161、洛谷、洛谷P1141(01迷宮迷宮)-尋找遞推過程尋找遞推過程以左

4、邊的迷宮為例，假如從第2行、第3列出發(fā)（行和列從1開始編號）令：lAi, j為迷宮第i行、第j列的數(shù)字，則Ai, j的取值為0或者1lTi, j為從第i行、第j列出發(fā)可到達(dá)的格子總數(shù)，則從第2行第3列出發(fā)，可到達(dá)的格子總數(shù)可記為T2, 3求解遞推過程如下（因為可到達(dá)的格子總數(shù)包含自身所以要加1）：l因為A2, 3 = 0，所以：T2, 3 = T2, 2 + T2, 4 + T3, 3 + 1l因為A2, 2 = 1，所以：T2, 2 = T1, 2 + 1l因為A2, 4 = 0，所以：T2, 4 = T1, 4 + T2, 5 + T4, 3 + 1l因為A3, 3 = 0，所以：T3,

5、3 = T3, 4 + 1l重復(fù)如上遞推步驟，直到某個格子不可到達(dá)相鄰的任何格子為止1000110110101001101001000100011001100011100110001172、洛谷、洛谷P1141(01迷宮迷宮)-定義數(shù)據(jù)結(jié)構(gòu)讀取迷宮信息定義數(shù)據(jù)結(jié)構(gòu)讀取迷宮信息因為輸入共有n行，每行n個字符，字符的取值只有0或1，字符間無空格。所以我們可以定義二維字符數(shù)組來保存迷宮的信息，同時以讀入字符串的方式讀取迷宮信息。由于字符串需要額外的空間保存結(jié)束符0，且n (1, 2)-(1, 1)-(1, 2)-(1, 1).重復(fù)的遞歸調(diào)用，無法結(jié)束。直至消耗完所有的棧內(nèi)存，導(dǎo)致程序運行崩潰。100

6、010101203、洛谷、洛谷P1141(01迷宮迷宮)-防止程序死循環(huán)崩潰（防止程序死循環(huán)崩潰（解決辦法解決辦法）我們可以按如下方式，防止重復(fù)的遞歸調(diào)用。定義二維數(shù)組標(biāo)記方格是否已經(jīng)被訪問1.在遞歸過程中過濾掉已經(jīng)訪問過的方格214、洛谷、洛谷P1141(01迷宮迷宮)-優(yōu)化運算時間優(yōu)化運算時間到此為止，雖然我們能求出所有方格可到達(dá)的方格數(shù)，但是如果需要求解的起點數(shù)量m太大時，就會超時。通過分析可以發(fā)現(xiàn)每個格子可以到達(dá)的格子數(shù)量有如下特點：l從某個格子出發(fā)，在求解過程中所經(jīng)過的所有格子，它們可到達(dá)的格子總數(shù)都相同。l假如從(2, 3)出發(fā)，可到達(dá)(2, 2)、(2, 4)、(3, 3)、(1

7、, 2)、(1, 4)、(2, 5)、(4, 3)、(3, 4).； 那么T2, 3 = T2, 2 = T2, 4 = T3, 3 = T1, 2 = T1, 4. 基于該特點，我們可以采用如下方式優(yōu)化程序的運行時間定義數(shù)組int P1000*10002，記錄從指定方格出發(fā)，可到達(dá)的所有方格的行下標(biāo)和列下標(biāo)。定義數(shù)組int R10001000，保存從每個方格出發(fā)，可到達(dá)的方格數(shù)量。若從(x, y)出發(fā)可達(dá)到的方格數(shù)為A，則求解過程中經(jīng)過的所有方格，它們可到達(dá)的方格數(shù)都為A。針對輸入的x, y，若Rxy 0 則可直接輸出結(jié)果，無需再次計算，節(jié)約計算時間224、洛谷、洛谷P1141(01迷宮迷宮)-優(yōu)化運算時間優(yōu)化運算時間23洛谷洛谷P3956(棋盤棋盤)-NOIP2017PJT3241、洛谷、洛谷P3956(棋盤棋盤)-編寫路徑遞推搜索模板編寫路徑遞推搜索模板252、洛谷、洛谷P3956(棋盤棋盤)-統(tǒng)計路徑中花費的金幣，計算花費的最少統(tǒng)計路徑中花費的金幣，計算花費的最少金幣金幣求所有路徑中的最小花費從一個棋格到另一個棋格需要花費的金幣263、洛谷、洛谷P3956(棋盤棋盤)-記錄路徑中棋格的顏色，完善魔法的限制記錄路徑中棋格的顏色，完善魔法的限制功能功能經(jīng)過的