3683: 观星

题目描述
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

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

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

80分代码

#include<bits/stdc++.h>
using namespace std;
int f[100005];
int s,n,m;
char a[1005][1005];
void x(int i,int j)
{
    if(i<0||j<0||i>=n||j>=m||a[i][j]=='.')return;
    a[i][j]='.',s++;
    x(i+1,j);x(i,j+1);
    x(i-1,j);x(i,j-1);
    x(i+1,j-1);x(i-1,j+1);
    x(i+1,j+1);x(i-1,j-1);
}
int main()
{
    int maxv=0,u=0;
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>a[i];
    set<int>se;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(a[i][j]=='*')
            {
                s=0,u++;
                x(i,j);
                se.insert(s);
                f[s]+=s;
                maxv=max(maxv,f[s]);
            }
        }
    }cout<<se.size()<<" "<<maxv;
}