1 条题解

  • 0
    @ 2024-12-24 10:06:03

    C++ :

    #include <iostream>
    #include <cstring>
    #include <cstdio>
    
    #define Maxn 203
    
    using namespace std;
    
    int G[Maxn][Maxn]={0};
    int n,m,color=0;
    int father[2*Maxn*Maxn]={0};
    int tot[Maxn*Maxn]={0};
    int ind[Maxn*Maxn]={0},outd[Maxn*Maxn]={0};
    bool flag[Maxn*Maxn]={0};
    
    char a[Maxn][Maxn],b[Maxn][Maxn];
    
    int find(int x)
    {
    	if(father[x]!=x) father[x]=find(father[x]);
    	return father[x];
    }
    
    void unionn(int x,int y)
    {
    	int r1=find(x);
    	int r2=find(y);
    	if(r1!=r2) father[r2]=r1;
    } 
    
    int abs(int x)
    {
    	if(x>0) return x;
    	return -x;
    }
    
    void build()
    {
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=m;j++)
    		{
    			if(a[i][j]=='X'||a[i][j]=='/')
    			{
    				if(!G[i][j-1])
    				{
    					G[i][j-1]=++color;
    					father[color]=color;
    				}
    				if(!G[i-1][j])
    				{
    					G[i-1][j]=++color;
    					father[color]=color;
    				}
    				outd[G[i][j-1]]++;
    				outd[G[i-1][j]]++;
    				unionn(G[i][j-1],G[i-1][j]);
    			}
    			if(a[i][j]=='X'||a[i][j]=='\\')
    			{
    				if(!G[i][j])
    				{
    					G[i][j]=++color;
    					father[color]=color;
    				}
    				if(!G[i-1][j-1])
    				{
    					G[i-1][j-1]=++color;
    					father[color]=color;
    				}
    				outd[G[i][j]]++;
    				outd[G[i-1][j-1]]++;
    				unionn(G[i][j],G[i-1][j-1]); 
    			}
    		}
    	}
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=m;j++)
    		{
    			if(b[i][j]=='X'||b[i][j]=='/')
    			{
    				if(!G[i][j-1])
    				{
    					G[i][j-1]=++color;
    					father[color]=color;
    				}
    				if(!G[i-1][j])
    				{
    					G[i-1][j]=++color;
    					father[color]=color;
    				}
    				ind[G[i][j-1]]++;
    				ind[G[i-1][j]]++;
    				unionn(G[i][j-1],G[i-1][j]); 
    			}
    			if(b[i][j]=='X'||b[i][j]=='\\')
    			{
    				if(!G[i][j])
    				{
    					G[i][j]=++color;
    					father[color]=color;
    				}
    				if(!G[i-1][j-1])
    				{
    					G[i-1][j-1]=++color;
    					father[color]=color;
    				}
    				ind[G[i][j]]++;
    				ind[G[i-1][j-1]]++;
    				unionn(G[i][j],G[i-1][j-1]);
    			}
    		}
    	}
    	for(int i=1;i<=color;i++)
    	{
    		if(ind[i]||outd[i])
    		{
    			int t=find(i);
    			if(!flag[t]) flag[t]=true;
    			tot[t]+=abs(ind[i]-outd[i]);
    		}
    	}
    }
    
    int main()
    {
    	cin>>n>>m;
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=m;j++)
    		{
    			cin>>a[i][j];
    		}
    	}
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=m;j++)
    		{
    			cin>>b[i][j];
    		}
    	}
    	
    	build();
    	
    	int ans=0;
    	for(int i=1;i<=color;i++)
    	{
    		if(find(i)==i)
    		{
    			if(tot[i]!=0) ans+=abs(tot[i])/2;
    			else ans++;
    		}
    	}
    	cout<<ans<<endl;
    	
    	return 0;
    }
    
    
    • 1

    信息

    ID
    1848
    时间
    1000ms
    内存
    128MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者