#402. 池塘数量
池塘数量
池塘数量
题目描述
农夫约翰有一片 的矩形土地。最近,由于降雨的原因,部分土地被水淹没了。
现在用一个字符矩阵表示他的土地。每个单元格内,如果包含雨水,则用 W 表示;如果不含雨水,则用 . 表示。
约翰想知道他的土地中形成了多少片池塘。每组相连的积水单元格集合可以看作一片池塘。
积水单元格与其上、下、左、右、左上、右上、左下、右下共八个方向的邻近积水单元格相连。
请输出矩阵中共有多少片相连的 W 块。
输入格式
第一行包含两个整数 和 。
接下来 行,每行包含 个字符,字符为 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
提示
注意:斜对角接触也算连通,不是只考虑上下左右四个方向。