Poj Solution 1683

http://poj.org/problem?id=1683

#include<iostream>
using namespace std;
int h[50][8],n,m;
char obj[8][8];
int sign[50][50];
int alive[50];

int can(int i,int j)
{int k;
    for(k=0;k<n;k++)
    if(h[i][k]*h[j][k]>0)break;

    if(k==n)return 1;
    else return 0;
}

void merage(int a,int b)
{int i;
for(i=0;i<n;i++)h[a][i]+=h[b][i];

for(i=0;i<n*m;i++){sign[a][i]+=sign[b][i];sign[i][a]+=sign[i][b];}
alive[b]=-a;
}


int main()
{int t,i,j,k,l,a,b,d;char c;
cin>>t;
for(;t>0;t--)
{cin>>n>>m;
for(i=0;i<n;i++)cin>>obj[i];

for(i=0;i<n*m;i++){alive[i]=1;}

for(i=0;i<n*m;i++)
{for(j=0;j<n;j++)h[i][j]=0;
h[i][i/m]=i%m+1;
}

for(i=0;i<n*m;i++)
for(j=0;j<n*m;j++)sign[i][j]=0;


while(1)
{cin>>i>>j>>c>>k>>l;if(i==0)break;
i--;j--;k--;l--;
if(c=='R'){a=i*m+j;b=k*m+l;
    while(alive[a]<1)a=-alive[a];
     while(alive[b]<1)b=-alive[b];
     merage(a,b);
    }
if(c=='N'){a=i*m+j;b=k*m+l;
        while(alive[a]<1)a=-alive[a];
         while(alive[b]<1)b=-alive[b];
    sign[b][a]=sign[a][b]=1;
    }
}
/*

for(i=0;i<n*m;i++)
{cout<<alive[i]<<" : ";
    for(j=0;j<n;j++)if(h[i][j])cout<<obj[j][h[i][j]-1];
cout<<endl;
}

for(i=0;i<n*m;i++)
{for(j=0;j<n*m;j++)cout<<sign[i][j];
cout<<endl;
}
*/
for(i=0;i<n*m;i++)
if(alive[i]>0)    
{ for(d=0;d<n;d++)
  if(d!=i)
  {k=-1;
    for(j=0;j<m;j++)    
    {l=d*m+j;while(alive[l]<1)l=-alive[l];
    if(l!=i&&!sign[i][l]&&alive[l]>0&&can(i,l)){if(k!=-1)break;else k=l;}
    }
    
   if(j==m&&k>=0){merage(i,k);d=n*m;i=-1;}
  }
}

//cout<<"**********"<<endl;
for(i=0;i<n*m;i++)
{for(j=0;j<n*m;j++)
 if(alive[j]>0&&h[j][0]==i+1)break;
 if(j<n*m){for(k=0;k<n;k++)cout<<obj[k][h[j][k]-1];cout<<endl;}
}
cout<<endl;
/*for(i=0;i<n*m;i++)
{cout<<alive[i]<<" : ";
            for(j=0;j<n;j++)if(h[i][j])cout<<obj[j][h[i][j]-1];
        cout<<endl;
}
                                                                              
for(i=0;i<n*m;i++)
{for(j=0;j<n*m;j++)cout<<sign[i][j];
    cout<<endl;
}

for(i=0;i<n*m;i++)
{for(k=0;k<n;k++)cout<<obj[k][h[i][k]-1];cout<<endl;}

cout<<"**********"<<endl;*/
} 

return 1;
}