题目名称	3438. [NOI Online 2020 3rd PJ]观星(民间数据)
输入输出	`noi_online2020_star.in/out`
难度等级	★☆
时间限制	1000 ms (1 s)
内存限制	256 MiB
测试数据	10
题目来源	syzhaoss 于2020-07-22加入
开放分组	全部用户
提交状态
分类标签	BFS DFS 种子填充
	分享题解

通过：19，提交：43，通过率：44.19%
syzhaoss	100	0.048 s	6.74 MiB	C++
ムラサメ	100	0.176 s	0.00 MiB	C++
斗鹰	100	0.450 s	0.00 MiB	C++
KHYL	100	0.520 s	0.00 MiB	C++
你太美	100	0.544 s	0.00 MiB	C++
┭┮﹏┭┮	100	0.597 s	0.00 MiB	C++
斗鹰	100	0.599 s	0.00 MiB	C++
DAZZ	100	0.610 s	30.37 MiB	C++
lihaoze	100	0.656 s	0.00 MiB	C++
在大街上倒立游泳	100	0.676 s	0.00 MiB	C++

关于观星(民间数据) 的近10条评论(全部评论)
论审错题的后果。。。城南花已开 2020-12-20 00:10 1楼

3438. [NOI Online 2020 3rd PJ]观星(民间数据)

★☆ 输入文件：noi_online2020_star.in 输出文件：noi_online2020_star.out 简单对比
时间限制：1 s 内存限制：256 MiB

【题目描述】

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$ 行中第 $i$ 行的第 $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$。

【来源】

NOI Online2020 入门组第三轮 Task 2