HDOJ(HDU).1241 Oil Deposits(DFS)

2019-11-10 17:27:45

字體：大中小

來源：轉載

供稿：網友

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

點我挑戰題目

從零開始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)]）

上代碼！

代碼總覽

/* 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;//發生越界的時候，終止遞歸 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] =='@')//當且僅當格子是@并且沒有訪問過 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循環遍歷整個地圖 for(int j =0; j<m; ++j){ if(!visit[i][j]&&mp[i][j] == '@'){//當且僅當格子是@并且沒有訪問過 cnt++; dfs(i,j); } } } printf("%d/n",cnt); } return 0;}

此題思路的實現就在于雙重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循環有異曲同工之妙。

上一篇：POJ 1905-Expanding Rods（二分法-中心移動距離）

下一篇：HDOJ(HDU).1258 Sum It Up (DFS)