點我挑戰題目
從零開始DFS HDOJ.1342 Lotto [從零開始DFS(0)] — DFS思想與框架/雙重DFS HDOJ.1010 Tempter of the Bone [從零開始DFS(1)] —DFS四向搜索/奇偶剪枝 HDOJ(HDU).1015 Safecracker [從零開始DFS(2)] —DFS四向搜索變種 HDOJ(HDU).1016 PRime Ring Problem (DFS) [從零開始DFS(3)] —小結：做DFS題目的關注點 HDOJ(HDU).1035 Robot Motion [從零開始DFS(4)]—DFS題目練習 HDOJ(HDU).1241 Oil Deposits(DFS) [從零開始DFS(5)] —DFS八向搜索/雙重for循環遍歷 HDOJ(HDU).1258 Sum It Up (DFS) [從零開始DFS(6)] —DFS雙重搜索/去重技巧 HDOJ(HDU).1045 Fire Net [從零開始DFS(７)]—DFS練習/check函數的思想
給出地圖規模n * m，地圖中 *（星號）代表空白， @ 代表油田。一群@聯通在一起稱為油田塊（此處的聯通為八方向聯通）。求地圖中油田塊的個數。
分析： 既然是求解油田塊的個數，自然先想到的辦法就是先處理一個油田塊，然后處理下一個油田塊……然后依次計數油田塊的個數，也就是每次處理一個油田塊的時候+1。我們按照這種方法來實現。 與之前的選數字，或者是給出指定入口求解是否能走地圖的題目不同。本題需要全部遍歷地圖，也就是說需要一個一個格子來遍歷地圖，采用雙重的for循環來實現。試想一下：當某一個格子是@時候，我們就從這個格子開始進行dfs，dfs的目的是處理掉與@相連的所有的@，于此同時計數+1。處理完成后，找到下一個是@的格子，再處理掉與此相連的@，計數+1。如此往復，直到處理完整個地圖，搜索結束。 那么不難看出，遞歸邊界就是：這個格子在地圖外邊。進行遞歸的條件是：當且僅當這個格子是@并且還沒有訪問過。 還有一點別忘記，此題判定@@相鄰的條件是八向聯通 也就是左上左下右上右下相鄰也算聯通，所以此題是八向搜素。 （可參見四向搜索的例題 HDOJ.1010 Tempter of the Bone [從零開始DFS(1)]）
上代碼！
此題思路的實現就在于雙重for循環代表遍歷整個地圖；
for(int i = 0;i <n; ++i){ for(int j =0; j<m; ++j){ if(!visit[i][j]&&mp[i][j] == '@'){ cnt++; dfs(i,j); } } }與之前的選數字的一個for循環有異曲同工之妙。
新聞熱點
疑難解答
