全國(guó)青少年信息學(xué)奧林匹克競(jìng)賽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ù)可以看出，迷宮中每個(gè)方格的行下標(biāo)和列下標(biāo)，都是從1開(kāi)始編號(hào)的。 為了便于處理，我們也可以將數(shù)組預(yù)留一部分空間，數(shù)組行下標(biāo)和列下標(biāo)也從1開(kāi)始編號(hào)l mapij取值為0，表示可以通過(guò)；取值為1，表示有障礙，不可通過(guò)l 因?yàn)閿?shù)組的行下標(biāo)和列下標(biāo)都從1開(kāi)始，且1=N、M(1, 2)-(1, 1).的重復(fù)遞歸調(diào)用，導(dǎo)致程序死循環(huán)，函數(shù)無(wú)法退出00001010063、迷宮求解、迷宮求解-定義數(shù)組標(biāo)記方格已經(jīng)被訪(fǎng)問(wèn)（定義數(shù)組標(biāo)記方格已經(jīng)被訪(fǎng)問(wèn)（解決死循環(huán)解決

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

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

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

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

6、010101203、洛谷、洛谷P1141(01迷宮迷宮)-防止程序死循環(huán)崩潰（防止程序死循環(huán)崩潰（解決辦法解決辦法）我們可以按如下方式，防止重復(fù)的遞歸調(diào)用。定義二維數(shù)組標(biāo)記方格是否已經(jīng)被訪(fǎng)問(wèn)1.在遞歸過(guò)程中過(guò)濾掉已經(jīng)訪(fǎng)問(wèn)過(guò)的方格214、洛谷、洛谷P1141(01迷宮迷宮)-優(yōu)化運(yùn)算時(shí)間優(yōu)化運(yùn)算時(shí)間到此為止，雖然我們能求出所有方格可到達(dá)的方格數(shù)，但是如果需要求解的起點(diǎn)數(shù)量m太大時(shí)，就會(huì)超時(shí)。通過(guò)分析可以發(fā)現(xiàn)每個(gè)格子可以到達(dá)的格子數(shù)量有如下特點(diǎn)：l從某個(gè)格子出發(fā)，在求解過(guò)程中所經(jīng)過(guò)的所有格子，它們可到達(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. 基于該特點(diǎn)，我們可以采用如下方式優(yōu)化程序的運(yùn)行時(shí)間定義數(shù)組int P1000*10002，記錄從指定方格出發(fā)，可到達(dá)的所有方格的行下標(biāo)和列下標(biāo)。定義數(shù)組int R10001000，保存從每個(gè)方格出發(fā)，可到達(dá)的方格數(shù)量。若從(x, y)出發(fā)可達(dá)到的方格數(shù)為A，則求解過(guò)程中經(jīng)過(guò)的所有方格，它們可到達(dá)的方格數(shù)都為A。針對(duì)輸入的x, y，若Rxy 0 則可直接輸出結(jié)果，無(wú)需再次計(jì)算，節(jié)約計(jì)算時(shí)間224、洛谷、洛谷P1141(01迷宮迷宮)-優(yōu)化運(yùn)算時(shí)間優(yōu)化運(yùn)算時(shí)間23洛谷洛谷P3956(棋盤(pán)棋盤(pán))-NOIP2017PJT3241、洛谷、洛谷P3956(棋盤(pán)棋盤(pán))-編寫(xiě)路徑遞推搜索模板編寫(xiě)路徑遞推搜索模板252、洛谷、洛谷P3956(棋盤(pán)棋盤(pán))-統(tǒng)計(jì)路徑中花費(fèi)的金幣，計(jì)算花費(fèi)的最少統(tǒng)計(jì)路徑中花費(fèi)的金幣，計(jì)算花費(fèi)的最少金幣金幣求所有路徑中的最小花費(fèi)從一個(gè)棋格到另一個(gè)棋格需要花費(fèi)的金幣263、洛谷、洛谷P3956(棋盤(pán)棋盤(pán))-記錄路徑中棋格的顏色，完善魔法的限制記錄路徑中棋格的顏色，完善魔法的限制功能功能經(jīng)過(guò)的