Poj2386 Lake Counting

发表于 | 更新于: | 分类于 ， ， | | 阅读数
字数统计: 442 | 阅读时长 ≈ 2

Description

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.

Input

* 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.

Output

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

Sample Input

1
2
3
4
5
6
7
8
9
10
11
10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

Sample Output

1
3

Analysis

DFS板题，从任意的w开始，不断把邻接的部分用.代替，1次DFS后与初始这个w连接的所有w就全都被替换成.，因此直到图中不再存在w为止，总共进行的DFS次数就是答案。8个方向对应8个状态转移，每个格子作为DFS的参数最多调用一次，时间复杂度为O(8nm)=O(nm)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
using namespace std;
int N, M;
char field[100][100];
void dfs(int x, int y)
{
	field[x][y] = '.';
	for (int dx = -1; dx <= 1; dx++)
	{
		for (int dy = -1; dy <= 1; dy++)
		{
			int nx = x + dx;
			int ny = y + dy;
			if (0 <= nx && nx < N && 0 <= ny && ny < M&&field[nx][ny] == 'W')
				dfs(nx, ny);
		}
	}
	return;
}
int main()
{
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> field[i][j];
		}
	}
	int res = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (field[i][j] == 'W')
			{
				dfs(i, j);
				res++;
			}
		}
	}
	cout << res << endl;
	return 0;
}