OI题库

【题目描述】

由于最近的降雨，农夫约翰的牧场里到处都是水坑。约翰的牧场用一个由 N x M (1 <= N <= 100; 1 <= M <= 100) 个小正方形组成的矩形表示。每个小正方形要么有积水('W')，要么是干燥的土地('.')。农夫约翰想算出他的牧场中形成了几个池塘（连通的水沟）。一些连通的小正方形组成一个池塘。八连通的积水被认为是连在一起的。如下图：

***
*W*
***

每个小正方形和与其相邻的8个小正方形（在不超出边境的情况下）是连在一起的。八连通指的是上图中相对W的*部分。
现给出一个约翰的农场的示意图，请你确定他有多少个池塘。

八连通区域指的是从区域内每一象素出发，可通过八个方向，即上、下、左、右、左上、右上、左下、右下这八个方向的移动的组合，在不越出区域的前提下，到达区域内的任意象素。
——维基百科

【输入格式】

第1行：用一个空格隔开的两个整数 N 和 M。
第2..N+1行：每行输入都代表约翰牧场的一行，有M个字符，每个字符为'W'或'.'，字符之间没有空格。

【输出格式】

第1行：约翰的牧场中的池塘数。

【样例输入】

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

【提示】

输出细节：有三个池塘：一个在左上角，一个在左下角，还有一个贴着右边。

【题目来源】

POJ 2386

译/丁泽方