HDOJ(HDU).1241 Oil Deposits(DFS) [從零開(kāi)始DFS(5)]

點(diǎn)我挑戰(zhàn)題目

從零開(kāi)始DFS HDOJ.1342 Lotto [從零開(kāi)始DFS(0)] — DFS思想與框架/雙重DFS HDOJ.1010 Tempter of the Bone [從零開(kāi)始DFS(1)] —DFS四向搜索/奇偶剪枝 HDOJ(HDU).1015 Safecracker [從零開(kāi)始DFS(2)] —DFS四向搜索變種 HDOJ(HDU).1016 PRime Ring Problem (DFS) [從零開(kāi)始DFS(3)] —小結(jié)：做DFS題目的關(guān)注點(diǎn) HDOJ(HDU).1035 Robot Motion [從零開(kāi)始DFS(4)]—DFS題目練習(xí) HDOJ(HDU).1241 Oil Deposits(DFS) [從零開(kāi)始DFS(5)] —DFS八向搜索/雙重for循環(huán)遍歷 HDOJ(HDU).1258 Sum It Up (DFS) [從零開(kāi)始DFS(6)] —DFS雙重搜索/去重技巧 HDOJ(HDU).1045 Fire Net [從零開(kāi)始DFS(７)]—DFS練習(xí)/check函數(shù)的思想

題意分析

給出地圖規(guī)模n * m，地圖中 *（星號(hào)）代表空白， @ 代表油田。一群@聯(lián)通在一起稱(chēng)為油田塊（此處的聯(lián)通為八方向聯(lián)通）。求地圖中油田塊的個(gè)數(shù)。

分析： 既然是求解油田塊的個(gè)數(shù)，自然先想到的辦法就是先處理一個(gè)油田塊，然后處理下一個(gè)油田塊……然后依次計(jì)數(shù)油田塊的個(gè)數(shù)，也就是每次處理一個(gè)油田塊的時(shí)候+1。我們按照這種方法來(lái)實(shí)現(xiàn)。 與之前的選數(shù)字，或者是給出指定入口求解是否能走地圖的題目不同。本題需要全部遍歷地圖，也就是說(shuō)需要一個(gè)一個(gè)格子來(lái)遍歷地圖，采用雙重的for循環(huán)來(lái)實(shí)現(xiàn)。試想一下：當(dāng)某一個(gè)格子是@時(shí)候，我們就從這個(gè)格子開(kāi)始進(jìn)行dfs，dfs的目的是處理掉與@相連的所有的@，于此同時(shí)計(jì)數(shù)+1。處理完成后，找到下一個(gè)是@的格子，再處理掉與此相連的@，計(jì)數(shù)+1。如此往復(fù)，直到處理完整個(gè)地圖，搜索結(jié)束。 那么不難看出，遞歸邊界就是：這個(gè)格子在地圖外邊。進(jìn)行遞歸的條件是：當(dāng)且僅當(dāng)這個(gè)格子是@并且還沒(méi)有訪問(wèn)過(guò)。 還有一點(diǎn)別忘記，此題判定@@相鄰的條件是八向聯(lián)通 也就是左上左下右上右下相鄰也算聯(lián)通，所以此題是八向搜素。 （可參見(jiàn)四向搜索的例題 HDOJ.1010 Tempter of the Bone [從零開(kāi)始DFS(1)]）

上代碼！

代碼總覽

此題思路的實(shí)現(xiàn)就在于雙重for循環(huán)代表遍歷整個(gè)地圖；

與之前的選數(shù)字的一個(gè)for循環(huán)有異曲同工之妙。