问题 3683 --观星

3683: 观星★★★

时间限制: 1 Sec  内存限制: 512 MB
提交: 353  解决: 223
[提交][状态][命题人:]

题目描述

Jimmy和Symbol约好一起看星星,浩瀚的星空可视为一个长为N、宽为M的矩阵,矩阵中共有N×M个位置,一个位置可以用坐标(i,j)(1<=i<=N,1<=j<=M)来表示。每个位置上可能是空的,也可能有一颗星星。

对于一个位置(i, j),与其相邻的位置有左边、左上、上面、右上、右边、右下、下面、左下8个位置。相邻位置上的星星被视为同一个星座,这种关系有传递性,例如若(1,1), (1,2), (1,3)三个位置上都有星星,那么这三个星星视为同一个星座。包含的星星数量相同的星座被视为一个星系(一个星系中的星座不一定相邻),星系的大小为星系中包含的所有星星数量。

由于Symbol太喜欢星系了,他就想考一考Jimmy,让Jimmy求出星空中有多少个星系,他还想知道,最大的星系有多大。

输入

第一行两个整数N,M表示矩阵的长宽。

接下来N行每行M个字符,每个字符只可能是'.'或'*'(不含引号,下同)。这N行中第i行的第j个字符是'*'表示位置(i,j)上有一个星星,否则表示它是空的。

对于20%的数据,N,M<=20,最大星系大小不超过200

对于50%的数据,N,M<=400

对于70%的数据,N,M<=1100

对于100%的数据,2<=N,M<=1500,最大星系大小不超过100000

输出

仅一行两个整数,用空格分隔开,分别表示星系的数量与最大星系的大小。

样例输入
Copy
样例输入1:
5 7
*......
..**..*
.*...*.
...*...
....*..
样例输入2:
10 10
**..**.**.
***....*..
*...**.**.
...*..*...
..........
**...**.*.
..*.*....*
..........
***..*.*..
.***..*...
样例输出
Copy
样例输出1:
3 4
样例输出2:
4 12

提示

来源

[提交][状态]