Responsive image

问题 D: 农场中的池塘

问题 D: 农场中的池塘

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 75
[提交][状态][讨论版][命题人:]

题目描述

小h觉得学习算法太难了，于是决定回家种地，他承包了一个N*M的矩形土地，但是由于降雨的原因，部分土地被水淹没了。现在，小h想知道他的土地中形成了多少片池塘。
现在用一个字符矩阵来表示他的土地。
每个单元格内，如果包含雨水，则用“W”表示，如果不包含雨水，则用“.”表示。
每组相连的积水单元格集合可以看作是一片池塘。
每个单元格视为与其上、下、左、右、左上、右上、左下、右下八个相邻单元格相连、
请你输出共有多少片池塘，即矩阵中共有多少片相连的“W”块。

输入描述

第一行包含两个整数N和M
接下来N行，每行包含M格字符，字符为“W"或“.”，用以表示矩形土地的积水状况，字符之间没有空格。

输出描述

输出一个整数，表示池塘数目。

样例输入

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

提示

1 <= N,M <= 1000

[提交][状态]
ACM算法攻关部