油田”問(wèn)題是一個(gè)比較經(jīng)典的體現(xiàn)DFS思想的題目，經(jīng)過(guò)學(xué)習(xí)，對(duì)DFS也有了一點(diǎn)理解，下面介紹下這個(gè)題目~

題目來(lái)源：

Mid-Central USA 1997,ZOJ1709,POJ1562

題目描述：

GeoSurvComp地質(zhì)探測(cè)公司負(fù)責(zé)探測(cè)地下油田。每次GeoSurvComp公司都是在一塊長(zhǎng)方形的土地上來(lái)探測(cè)油田。在探測(cè)時(shí)，他們把這塊土地用網(wǎng)格分成若干個(gè)小塊，然后逐個(gè)分析每塊土地，用探測(cè)設(shè)備探測(cè)地下是否有油田。土地底下有油田則成為pocket，如果兩個(gè)pocket相鄰，則認(rèn)為是同一塊油田，油田可能覆蓋多個(gè)pocket。試計(jì)算長(zhǎng)方形的土地上有多少個(gè)不同的油田。

輸入描述：

輸入文件中包含多個(gè)測(cè)試數(shù)據(jù)，每個(gè)測(cè)試數(shù)據(jù)描述了一個(gè)網(wǎng)格。每個(gè)網(wǎng)格數(shù)據(jù)的第1行為兩個(gè)整數(shù)：m、n，分別表示網(wǎng)格的行和列；如果m=0，則表示輸入結(jié)束，否則1<=m<=100，1<=n<=100。接下來(lái)有m行數(shù)據(jù)，每行數(shù)據(jù)有n個(gè)字符（不包括行結(jié)束符）。每個(gè)字符代表一個(gè)小方塊，如果為“*”，則代表沒(méi)有石油，如果為“@”，則代表有石油，是一個(gè)pocket。

輸出描述：

對(duì)輸入文件中的每個(gè)網(wǎng)格，輸出網(wǎng)格中不同的油田數(shù)目。如果兩塊不同的pocket在水平、垂直或者對(duì)角線方向上相鄰，則被認(rèn)為屬于同一塊油田。每塊油田所包含的pocket數(shù)目不會(huì)超過(guò)100。

樣例輸入：

5 5

****@

*@@*@

*@**@

@@@*@

@@**@

樣例輸出：

2

下面還是老套路，貼上源碼+注釋，希望能加深理解~

Code：

[cpp]?view plaincopyprint?

#include<iostream>??

using?namespace?std;??

??

char?grid[101][101];????//網(wǎng)格??

int?n,?m;???????//行、列??

//一個(gè)網(wǎng)格的8個(gè)方向??

int?dir[8][2]?=?{?{-1,?-1},?{-1,?0},?{-1,?1},?{0,?-1},?{0,?1},?{1,?-1},?{1,?0},?{1,?1}?};??

??

//從（x,y）進(jìn)行深度優(yōu)先遍歷??

void?DFS(int?x,?int?y)??

{??

????int?xx,?yy;??

????grid[x][y]?=?'*';???????//將grid中訪問(wèn)過(guò)的方塊設(shè)置成‘*’，防止重復(fù)訪問(wèn)~??

????for(int?i?=?0;?i?<?8;?i++)??

????{??

????????xx?=?x?+?dir[i][0];??

????????yy?=?y?+?dir[i][1];??

????????if(xx<0?||?xx>=n?||?yy<0?||?yy>=m)?continue;????//越界終止本次循環(huán)??

????????if(grid[xx][yy]?==?'@')?DFS(xx,?yy);????????????//如果方格還是‘@’，則繼續(xù)搜索??

????}??

}??

??

int?main()??

{??

????int?i,?j;???//循環(huán)變量??

????int?count;??//油田數(shù)量計(jì)數(shù)??

????while(scanf("%d%d",?&n,?&m))??

????{??

????????if(n?==?0?&&?m?==?0)?break;??

????????count?=?0;??

????????memset(grid,?0,?sizeof(grid));??

??

????????for(i?=?0;?i?<?n;?i++)?scanf("%s",?grid[i]);??

????????for(i?=?0;?i?<?n;?i++)??

????????????for(j?=?0;?j?<?m;?j++)??

????????????????if(grid[i][j]?==?'@')?{?DFS(i,?j);?count++;?}???//在（i,j）遍歷，并且遍歷了一個(gè)“油田”，計(jì)數(shù)器加1??

????????printf("%d\n",?count);??

????}??

????return?0;??

}??

運(yùn)行結(jié)果：

Ps：如有bug，歡迎拍磚~

總結(jié)

以上是生活随笔為你收集整理的实现DFS之“油田”的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。