實現DFS之“農田灌溉”

這也是一道利用了DFS的題目,先說下我的思路:用一個二維陣列記錄每個字母所代表的含義(管道方向),用另一個二維陣列記錄4個方向的變換座標;隨後利用經典的DFS遞迴遍歷即可~(還要注意在方向的處理上前後要保持一致,否則很容易計算出錯 :| )

農田灌溉(Farm Irrigation)   

題目描述: 

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

Benny農田的地圖是由描述每個正方形農田中水管型別的字母組成的矩陣。例如,如果農田的地圖為: ADC FJK IHE 

則農田中水管分佈如圖2所示。 

某些正方形農田的中心有水源,因此水可以沿著水管從一個正方形農田流向另一個正方形農田。如果水可以流經某個正方形農田,則整個正方形農田可以全部灌溉到。 Benny想知道至少需要多少個水源,以保證整個農田都能被灌溉到? 例如,圖2所示的農田至少需要3個水源,圖中的圓點表示每個水源。  
輸入描述:  
輸入檔案中包含多個測試資料。每個測試資料的第1行為兩個整數M和N,表示農田中有M行,每行有N個正方形。接下來有M行,每行有N個字元。字元的取值為’A’~’K’,表示對應正方形農田中水管的型別。當M或N取負值時,表示輸入檔案結束。如果M和N的值為正數,則其取值範圍是1≤M, N≤50。  
輸出描述:  
對輸入檔案中的每個測試資料所描述的農田,輸出佔一行,為求得的所需水源數目的最小值。  

樣例輸入:  

2 2

DK

HF

3 3

ADC

FJK

IHE

-1 -1

樣例輸出: 

2 3

閒話少敘,直接上程式碼 註釋~

Code:

#include<iostream>
using namespace std;
#define MAXN 50
char map[MAXN][MAXN];	//地圖
int M, N;				//M:農田行數,N:每行的正方形個數
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}
};		//每種農田塊對應的4個管道方向(-1為左或上、1為右或下、0為沒有)。
void DFS(int x, int y)
{
int xx, yy;
char temp = map[x][y];		//暫存當前農田塊的形狀,便於後面的比較~
map[x][y] = 'Y';			//覆蓋原來農田為已遍歷
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)	
{//若相鄰兩塊農田管道能“接上”,即管道方向對應的值之積為-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地圖賦值
//遍歷地圖、遞迴計數
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,歡迎拍磚~
:)