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;
}