1 solutions

  • 0
    @ 2025-2-27 15:52:35
    #include<bits/stdc++.h>
    using namespace std;
    int n,m;
    const int N=1510;
    const int M=100010;
    bool st[N][N];//标记是否走过 
    char g[N][N]; //地图 
    int cnt[M]; //每个星系的数目 
    int dx[]={-1,-1,-1,0,0,1,1,1}; //周围的方向 
    int dy[]={-1,0,1,-1,1,-1,0,1};
    typedef pair<int,int> PII;
    #define x first
    #define y second
    int bfs(int x,int y) //宽度优先搜索 
    {
    	queue<PII> q;
    	int res=1;
    	q.push({x,y});
    	while(q.size())
    	{
    		auto t=q.front();
    		q.pop();
    		for(int i=0;i<8;i++)
    		{
    			int a=t.x+dx[i],b=t.y+dy[i];
    			if(a<1||a>n||b<1||b>m) continue;
    			if(g[a][b]=='.') continue;
    			if(st[a][b]==1) continue;
    			res++;
    			st[a][b]=1;
    			q.push({a,b});
    			
    		}
    	}
    	return res;
    }
    int main()
    {
    	cin>>n>>m;
    	for(int i=1;i<=n;i++) //获取地图 
    	{
    		for(int j=1;j<=m;j++)
    		{
    			cin>>g[i][j];
    		}
    	}
    	for(int i=1;i<=n;i++) //预处理每个星系 
    	{
    		for(int j=1;j<=m;j++)
    		{
    			if(g[i][j]=='*'&&st[i][j]==0)
    			{
    				st[i][j]=1;
    				int now=bfs(i,j);
    				cnt[now]++;
    			}
    		}
    	}
    	int ans1=0,ans2=0;
    	for(int i=1;i<=100000;i++) //计算星系数量和最大星系大小 
    	{
    		if(cnt[i]>0)
    		{
    			ans1++;
    			ans2=max(ans2,i*cnt[i]);
    		}
    	}
    	cout<<ans1<<" "<<ans2<<endl;
    	return 0;
    } 
    
    • 1

    Information

    ID
    2156
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    5
    Tags
    # Submissions
    22
    Accepted
    6
    Uploaded By