#402. 池塘数量

池塘数量

池塘数量

题目描述

农夫约翰有一片 N×MN\times M 的矩形土地。最近,由于降雨的原因,部分土地被水淹没了。

现在用一个字符矩阵表示他的土地。每个单元格内,如果包含雨水,则用 W 表示;如果不含雨水,则用 . 表示。

约翰想知道他的土地中形成了多少片池塘。每组相连的积水单元格集合可以看作一片池塘。

积水单元格与其上、下、左、右、左上、右上、左下、右下共八个方向的邻近积水单元格相连。

请输出矩阵中共有多少片相连的 W 块。

输入格式

第一行包含两个整数 NN 和 MM。

接下来 NN 行,每行包含 MM 个字符,字符为 W 或 .,字符之间没有空格。

输出格式

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

数据范围

1≤N,M≤10001\le N,M\le 1000。

输入输出样例

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

提示

注意:斜对角接触也算连通,不是只考虑上下左右四个方向。