這也是一道利用了DFS的題目，先說下我的思路：用一個二維數(shù)組記錄每個字母所代表的含義（管道方向），用另一個二維數(shù)組記錄4個方向的變換坐標；隨后利用經(jīng)典的DFS遞歸遍歷即可~（還要注意在方向的處理上前后要保持一致，否則很容易計算出錯 ：| ）

農(nóng)田灌溉(Farm Irrigation) ??

題目描述：?

Benny有一大片農(nóng)田需要灌溉。農(nóng)田是一個長方形，被分割成許多小的正方形。每個正方形中都安裝了水管。不同的正方形農(nóng)田中可能安裝了不同的水管。一共有11種水管，分別用字母A～K標明，如圖1所示。?

Benny農(nóng)田的地圖是由描述每個正方形農(nóng)田中水管類型的字母組成的矩陣。例如，如果農(nóng)田的地圖為： ADC FJK IHE?

則農(nóng)田中水管分布如圖2所示。?

某些正方形農(nóng)田的中心有水源，因此水可以沿著水管從一個正方形農(nóng)田流向另一個正方形農(nóng)田。如果水可以流經(jīng)某個正方形農(nóng)田，則整個正方形農(nóng)田可以全部灌溉到。 Benny想知道至少需要多少個水源，以保證整個農(nóng)田都能被灌溉到？ 例如，圖2所示的農(nóng)田至少需要3個水源，圖中的圓點表示每個水源。 ?
輸入描述： ?
輸入文件中包含多個測試數(shù)據(jù)。每個測試數(shù)據(jù)的第1行為兩個整數(shù)M和N，表示農(nóng)田中有M行，每行有N個正方形。接下來有M行，每行有N個字符。字符的取值為'A'～'K'，表示對應正方形農(nóng)田中水管的類型。當M或N取負值時，表示輸入文件結束。如果M和N的值為正數(shù)，則其取值范圍是1≤M, N≤50。 ?
輸出描述： ?
對輸入文件中的每個測試數(shù)據(jù)所描述的農(nóng)田，輸出占一行，為求得的所需水源數(shù)目的最小值。 ?

樣例輸入： ?

2 2

DK

HF

3 3

ADC

FJK

IHE

-1 -1

樣例輸出：?

2 3

閑話少敘，直接上代碼+注釋~

Code：

[cpp]?view plaincopyprint?

#include<iostream>??

using?namespace?std;??

??

#define?MAXN?50??

char?map[MAXN][MAXN];???//地圖??

int?M,?N;???????????????//M:農(nóng)田行數(shù)，N:每行的正方形個數(shù)??

??

int?dir[4][2]?=?{?{-1,?0},?{1,?0},?{0,?-1},?{0,?1}?};???//管道坐標變換的四個方向：對應的順序上下左右。??

int?dirO[11][4]?=?{??

????{-1,?0,?-1,?0},?{-1,?0,?0,?1},?{0,?1,?-1,?0},??

????{0,?1,?0,?1},?{-1,?1,?0,?0},?{0,?0,?-1,?1},??

????{-1,?0,?-1,?1},?{-1,?1,?-1,?0},?{0,?1,?-1,?1},??

????{-1,?1,?0,?1},?{-1,?1,?-1,?1}??

????};??????//每種農(nóng)田塊對應的4個管道方向(-1為左或上、1為右或下、0為沒有)。??

??

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

{??

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

????char?temp?=?map[x][y];??????//暫存當前農(nóng)田塊的形狀，便于后面的比較~??

????map[x][y]?=?'Y';????????????//覆蓋原來農(nóng)田為已遍歷??

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

????{??

????????//計算下一個方向的坐標。??

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

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

????????if(xx<0?||?xx>=MAXN?||?yy<0?||?yy>=MAXN)?continue;??????//越界,跳至下一個方向的判斷??

??????????

????????//方向所代表的值：上0、下1、左2、右3。??

??????

????????//如果向上走(0)或向左走(2)，比如向左走則判斷原坐標的“左”管道和下一個方向坐標的“右”管道，方向所代表的值+1??

????????if(i?==?0?||?i?==?2)??????

????????{//若相鄰兩塊農(nóng)田管道能“接上”，即管道方向對應的值之積為-1??

????????????if(map[xx][yy]!='Y'?&&?dirO[temp-'A'][i]*dirO[map[xx][yy]-'A'][i+1]==-1)?DFS(xx,?yy);??

????????}??

????????//否則為向下走(1)或向右走(3)，比如向下走則判斷原坐標的“下”管道和下一個方向坐標的“上”管道。對應方向所代表的值-1??

????????else?if(map[xx][yy]!='Y'?&&?dirO[temp-'A'][i]*dirO[map[xx][yy]-'A'][i-1]==-1)?DFS(xx,?yy);??

????}??

}??

int?main()??

{??

????int?i,?j;??

????int?count;??

????while(scanf("%d%d",?&M,?&N))??

????{??

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

????????if(M?<?0?||?N?<?0)?break;??

????????for(i?=?0;?i?<?M;?i++)?scanf("%s",?map[i]);??????????//以行為單位為map地圖賦值??

????????//遍歷地圖、遞歸計數(shù)??

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

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

????????????????if(map[i][j]?!=?'Y')?{?DFS(i,?j);?count++;?}??

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

????}??

????return?0;??

}??

運行結果：

如有Bug，歡迎拍磚~ ?：）

總結

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

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