【原創】【Openjudge】1388 ： Lake Counting

1388:Lake Counting

總時間限制: 

1000ms 

記憶體限制: 

65536kB

描述

Due to recent rains, water has pooled in various places in Farmer John's field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water ('W') or dry land ('.'). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors.

Given a diagram of Farmer John's field, determine how many ponds he has.

輸入

* Line 1: Two space-separated integers: N and M

* Lines 2..N+1: M characters per line representing one row of Farmer John's field. Each character is either 'W' or '.'. The characters do not have spaces between them.

輸出

* Line 1: The number of ponds in Farmer John's field.

樣例輸入

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.      

樣例輸出

3      

提示

OUTPUT DETAILS:

There are three ponds: one in the upper left, one in the lower left,and one along the right side.

來源

USACO 2004 Novembe

題目大意  

大雨過後，農夫John的農場 被水淹沒不知所措有了積水，農場地圖中‘W’代表積水，'.'代表幹燥的土地。八連通的積水在同一個水窪裡。農夫John想知道農場裡有多少水窪。

這是一道搜尋題。與其他搜尋題一樣，都是不斷地搜尋，直到達到目的。但是，這道題的目的是什麼呢？

目的是求出有多少水窪，如果遞歸的話，怎麼才能知道求出了數量呢？

是以這樣，不能單純的隻調用一次函數（主程式中），否則最多隻會找出一個水窪。

我一開始是這樣想的，把每個水窪隻留下一個W，其餘換成幹燥，最後再看有幾個W。可是這樣搜尋的時候，留下的W也會被搜到，搜到就會變成'.'，答案就會是0。為了避免這個問題，需要設立一個輔助數組或者把這個W換成另一個字元，但是這樣既浪費時間也浪費空間（還浪費我的腦容量）。

于是我把函數寫在循環裡，把一個水窪消滅幹淨後，水窪數量就加1。我用DFS，BFS實作了這個想法。

代碼如下：

DFS:

#include<iostream>
#include<cstdio>
using namespace std;
int m,n,num;
int dr[8][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
char farm[120][120];
void search(int i,int j)
{
	farm[i][j]='.';
	for(int p=0;p<8;p++)
	{
		int x=i+dr[p][0],y=j+dr[p][1];  
		if(x>=0 && y>=0 && x<m && y<n && farm[x][y]=='W') search(x,y);
	}
}
int main()
{
	cin>>m>>n;
	for (int i=0;i<m;i++) scanf("%s",farm[i]);
	for (int i=0;i<m;i++)  
		for (int j=0;j<n;j++)  
			if (farm[i][j]=='W')
			{  
				search(i,j);  
				num++;  
			}  
   printf("%d\n",num);  
}
           

BFS:用結構體數組模拟隊列。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<stack>
using namespace std;
int m,n,num;
int dr[8][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,-1},{-1,1}};
char farm[120][120];
struct Epic
{
	int x,y;
};//x-x坐标，y-y坐标
void search(int i,int j)
{
	Epic p,q;
	p.x=i,p.y=j;
	queue <Epic> k;
	k.push(p);
	farm[i][j]='.';
	while(! k.empty() )
	{
		p=k.front();
		k.pop();
		for(int o=0;o<8;o++)
		{
			q.x=p.x+dr[o][0];
			q.y=p.y+dr[o][1];
			if (q.x>=0 && q.x<m && q.y>=0 && q.y<n)
				if (farm[q.x][q.y]=='W' )
				{
					k.push(q);
					farm[q.x][q.y]='.';
				}
		}
	}
}
int main()
{
	scanf("%d %d",&m,&n);
	
	for(int i=0;i<m;i++)
		scanf("%s",farm[i]);
	
	for(int i=0;i<m;i++)
		for(int j=0;j<n;j++)
			if(farm[i][j]=='W')
			{
				search(i,j);
				num++;
			}
				
/*
	for(int i=0;i<m;i++)
	{
		printf("\n");
		for(int j=0;j<n;j++)
			printf("%c",farm[i][j]);
	}
	printf("\n");
	*/

	printf("%d\n",num);
	return 0;
}