2 solutions

  • 1
    @ 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;
    } 
    
    • 0
      @ 2026-3-29 14:08:52
      #include<bits/stdc++.h>
      using namespace std;
      int n,m;
      const int N=1510,M=100010;
      int dx[]={-1,-1,-1,0,0,1,1,1};
      int dy[]={-1,0,1,-1,1,-1,0,1};
      bool st[N][N];
      char g[N][N];
      int cnt[M];
      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];
      		}
      	}
      	//	cout<<"???:?"<<endl; 
      	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]++;
      				//cout<<now<<endl;
      			}
      		}
      	}
      	//cout<<"???:?"; 
      	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
      3000ms
      Memory
      256MiB
      Difficulty
      5
      Tags
      # Submissions
      61
      Accepted
      12
      Uploaded By