问题 4766 --观星(本站数据)

4766: 观星(本站数据)

题目描述

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

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

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

输入

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

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

输出

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

样例输入输出

输入#1 复制
5 7
*......
..**..*
.*...*.
...*...
....*..
输出#1 复制
3 4
输入#2 复制
10 10
**..**.**.
***....*..
*...**.**.
...*..*...
..........
**...**.*.
..*.*....*
..........
***..*.*..
.***..*...
输出#2 复制
4 12

提示

对于 $20\%$ 的数据,$N,M\le 20$,最大星系大小不超过 $200$。
对于 $50\%$ 的数据,$N,M\le 400$。
对于 $70\%$ 的数据,$N,M\le 1100$。
对于 $100\%$ 的数据,$2\le N,M\le 1500$,最大星系大小不超过 $100000$。

序号 标题 作者 发表时间 费用 订购数 操作