POJ2386 Lake Counting

POJ2386 Lake Counting

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

Hint

OUTPUT DETAILS:

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

Answer

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
#include <cstdio>

using namespace std;

const int maxn=105;
int n, m, ans = 0;
char maze[maxn][maxn];

void dfs(int i, int j);

int main() {
scanf("%d %d", &n, &m);

for (int i = 0; i < n; ++i)
scanf("%s", &maze[i]);

for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
if (maze[i][j] == 'W') {
++ans;
dfs(i ,j);
}

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

void dfs(int i, int j) {
if (i < 0 || i >= n) return;
if (j < 0 || j >= m) return;
if (maze[i][j] == '.') return;

maze[i][j] = '.';

for (int dx = -1; dx <= 1; ++dx)
for (int dy = -1; dy <= 1; ++dy)
dfs(i+dx, j+dy);
}

Analysis

  1. 二维字符数组的输入问题,边界问题。
  2. 深度优先搜索遍历连通图,求连通子图的个数。
  3. 深度优先遍历的条件判定。
# POJ

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×