HDOJ(HDU).1241 Oil Deposits(DFS)

2019-11-10 17:39:55

字體：大中小

供稿：網(wǎng)友

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

點我挑戰(zhàn)題目

從零開始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)] —小結(jié)：做DFS題目的關(guān)注點 HDOJ(HDU).1035 Robot Motion [從零開始DFS(4)]—DFS題目練習(xí) HDOJ(HDU).1241 Oil Deposits(DFS) [從零開始DFS(5)] —DFS八向搜索/雙重for循環(huán)遍歷 HDOJ(HDU).1258 Sum It Up (DFS) [從零開始DFS(6)] —DFS雙重搜索/去重技巧 HDOJ(HDU).1045 Fire Net [從零開始DFS(７)]—DFS練習(xí)/check函數(shù)的思想

題意分析

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

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

上代碼！

代碼總覽

/* Title:HDOJ.1241 Author:pengwill Date:2017-2-8*/#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int n, m,visit[105][105],cnt;char mp[105][105];int spx[] = {0,1,0,-1,1,1,-1,-1};int spy[] = {1,0,-1,0,-1,1,1,-1};bool check(int x, int y){ if(x<0 || x>=n || y<0 || y>=m) return false; else return true;}void dfs(int x , int y){ if(!check(x,y)) return;//發(fā)生越界的時候，終止遞歸 visit[x][y] = 1; for(int i = 0;i <8 ;++i){ int nx = x+ spx[i]; int ny = y +spy[i]; if(visit[nx][ny] == 0 && mp[nx][ny] =='@')//當(dāng)且僅當(dāng)格子是@并且沒有訪問過 dfs(nx,ny); }}int main(){ while(scanf("%d%d",&n,&m) && n){ for(int i = 0; i<n;++i) scanf("%s",mp[i]); cnt = 0; memset(visit,0,sizeof(visit)); for(int i = 0;i <n; ++i){//采用雙重for循環(huán)遍歷整個地圖 for(int j =0; j<m; ++j){ if(!visit[i][j]&&mp[i][j] == '@'){//當(dāng)且僅當(dāng)格子是@并且沒有訪問過 cnt++; dfs(i,j); } } } printf("%d/n",cnt); } return 0;}

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

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); } } }

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

上一篇：poj1703 Find them, Catch them

下一篇：洛谷 P1006 傳紙條