2 条题解

  • 0
    #include<bits/stdc++.h>
    using namespace std;
    int dx[4]={-1,1,0,0};
    int dy[4]={0,0,-1,1};
    int num[1005][1005],p=0;
    int fa[1000005];
    int size[1000005];
    int n,m;
    char a[1005][1005];
    bool vis[1000005];
    int find(int x){
    	if(fa[x]==x){
    		return x;
    	}else{
    		return fa[x]=find(fa[x]);
    	}
    }
    void merge(int x,int y){
    	int fx=find(x);
    	int fy=find(y);
    	if(fx==fy){
    		return ;
    	}
    	if(size[fx]>size[fy]){
    		fa[fy]=fx;
    		size[fx]+=size[fy];
    	}else{
    		fa[fx]=fy;
    		size[fy]+=size[fx];
    	}
    }
    int main(){
    	cin>>n>>m;
    	for(int i=1;i<=n*m;i++){
    		fa[i]=i;
    		size[i]=1;
    	}
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=m;j++){
    			cin>>a[i][j];
    			num[i][j]=(++p);
    		}
    	}
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=m;j++){
    			if(a[i][j]=='.'){
    				for(int k=0;k<4;k++){
    					int b,c;
    					b=i+dx[k];
    					c=j+dy[k];
    					if(a[b][c]=='.'&&vis[find(num[b][c])]==0){
    						vis[find(num[b][c])]=1;
    						merge(num[i][j],num[b][c]);
    					}
    				}
    				for(int k=0;k<4;k++){
    					int b,c;
    					b=i+dx[k];
    					c=j+dy[k];
    					vis[find(num[b][c])]=0;
    				}
    			}
    		}
    	}
    	int ans=0;
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=m;j++){
    			int sum=0;
    			if(a[i][j]=='*'){
    				for(int k=0;k<4;k++){
    					int b,c;
    					b=i+dx[k];
    					c=j+dy[k];
    					if(a[b][c]=='.'&&vis[find(num[b][c])]==0){
    						vis[find(num[b][c])]=1;
    						sum+=size[find(num[b][c])];
    					}
    				}
    				for(int k=0;k<4;k++){
    					int b,c;
    					b=i+dx[k];
    					c=j+dy[k];
    					vis[find(num[b][c])]=0;
    				}
    			}
    			ans=max(ans,sum+1);
    		}
    	}
    	cout<<ans;
    	return 0;
    }
    
    • 0

      勿抄 不然CE你

      #include<bits/stdc++.h>
      using namespace std;
      
      const int N=1e6+10;
      const int M=1e3+10;
      int dx[10]={-1,1,0,0},dy[10]={0,0,-1,1};
      int num[M][M],p,ans=(-0x3f3f3f3f);
      int n,m,fa[N],siz[N];//siz存连通分量大小 
      bool vis[N];
      char a[M][M];
      
      void Memset()
      {
      	for(int i=1;i<=n*m;++i)
      	{
      		fa[i]=i;
      		siz[i]=1;
      	}
      }
      
      int find(int x)
      {
      	if(fa[x]==x)return x;
      	return fa[x]=find(fa[x]);
      }
      
      void merge(int x,int y)
      {
      	int fx=find(x),fy=find(y);
      	if(fx==fy)return;
      	if(siz[fx]<siz[fy])//把小的连通分量合并给大的
      	{
      		fa[fx]=fy;siz[fy]+=siz[fx];
      	}
      	else 
      	{
      		fa[fy]=fx;siz[fx]+=siz[fy];
      	}
      }
      
      int main()
      {
      	cin>>n>>m;
      	Memset();
      	for(int i=1;i<=n;++i)
      	{
      		for(int j=1;j<=m;++j)
      		{
      			cin>>a[i][j];
      			num[i][j]=(++p);
      		} 
      	}
      	for(int i=1;i<=n;++i)
      	{
      		for(int j=1;j<=m;++j)
      		{
      			if(a[i][j]=='.')
      			{
      				for(int k=0;k<4;++k)
      				{
      					int b=i+dx[k]int c=j+dy[k];
      					if(a[b][c]=='.')
      					{
      						merge(num[i][j],num[b][c]);
      					}
      				}
      			}
      		} 
      	}
      	
      	//把贫瘠变为肥沃 
      	for(int i=1;i<=n;++i)
      	{
      		for(int j=1;j<=m;++j)
      		{
      			int sum=0
      			if(a[i][j]=='*')
      			{
      				
      				for(int k=0;k<4;++k)
      				{
      					int b=i+dx[k];
      					int c=j+dy[k];
      					if(a[b][c]=='.' && vis[ find(num[b][c]) ]==0)
      					{
      						vis[ find(num[b][c]) =1;
      						sum+=siz[ find(num[b][c]) ];
      					}
      				}	
      				for(int k=0;k<4;++k)
      				{
      					int b=i+dx[k];int c=j+dy[k];
      					vis[ find(num[b][c) ]=0;
      				}	
      			}
      			ans=max(ans,sum+1);
      		} 
      	}
      	cout<<ans;
      	return 0; 
      }
      
      • 1

      信息

      ID
      3150
      时间
      1000ms
      内存
      256MiB
      难度
      6
      标签
      (无)
      递交数
      24
      已通过
      7
      上传者