Figure 1 The gray part represents a
hole, and the numbers means its owner, i.e. the two gray parts in the lower left
corner means the two holes belongs to mouse 2.
Kudo think it is very
interesting, so she makes a lot of boxes, and sign them “Saya’s House”, “Riki’s
House”, “Lin’s House” and so on.
Figure 2 The jointed gray parts represent the same hole.
At last, she combines them together to make a large box as shown in Figure 2.
Figure 3 How Kudo combines the
boxes.
4 1 2 2 1 1 2 2 1 1 1 1 2 2 1 1 2 2 0 0
Case 1: 1 2 1 2 3 4 3 4
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<string> 6 #include<cmath> 7 #define N 104 8 #define M 1000 9 using namespace std; 10 int n,d[4][N][M+5],fa[M*M+5],num[M*M+5];//u,d,l,r 11 int find(int x){ 12 if(x==fa[x]) 13 return x; 14 return fa[x]=find(fa[x]); 15 } 16 void merge(int x,int y){ 17 int fx=find(x); 18 int fy=find(y); 19 if(fx==fy) 20 return ; 21 fa[fx]=fy; 22 return ; 23 } 24 int cal(int k,int i){ 25 if(k==0) 26 return i; 27 if(k==1) 28 return n*n-n+i; 29 if(k==2) 30 return i*n; 31 return i*n+n-1; 32 } 33 int main() 34 { 35 int m,i,j,k,cnt; 36 int ics=0; 37 while(~scanf("%d%d",&n,&m)){ 38 if(!n&&!m) 39 break; 40 for(i=0;i<n;i++){ 41 for(k=0;k<4;k++){ 42 for(j=0;j<m;j++){ 43 scanf("%d",&d[k][i][j]); 44 } 45 } 46 } 47 cnt=1; 48 for(i=0;i<n;i++){ 49 memset(num,0,sizeof(num)); 50 for(k=0;k<4;k++){ 51 for(j=0;j<m;j++){ 52 if(!num[d[k][i][j]]){ 53 num[d[k][i][j]]=cnt++; 54 } 55 d[k][i][j]=num[d[k][i][j]]; 56 } 57 } 58 } 59 for(i=0;i<=cnt;i++) 60 fa[i]=i; 61 n=sqrt((double)(n+0.5)); 62 for(i=0;i<n;i++){ 63 for(j=0;j<n-1;j++){ 64 for(k=0;k<m;k++){ 65 merge(d[3][i*n+j][k],d[2][i*n+j+1][k]); 66 } 67 } 68 } 69 for(i=0;i<n-1;i++){ 70 for(j=0;j<n;j++){ 71 for(k=0;k<m;k++){ 72 merge(d[1][i*n+j][k],d[0][i*n+j+n][k]); 73 } 74 } 75 } 76 printf("Case %d:\n",++ics); 77 cnt=1; 78 memset(num,0,sizeof(num)); 79 for(k=0;k<4;k++) 80 for(i=0;i<n;i++){ 81 for(j=0;j<m;j++){ 82 int t=cal(k,i); 83 d[k][t][j]=find(d[k][t][j]); 84 if(!num[d[k][t][j]]) 85 num[d[k][t][j]]=cnt++; 86 printf("%d ",num[d[k][t][j]]); 87 } 88 } 89 printf("\n\n"); 90 } 91 return 0; 92 }
原文：http://www.cnblogs.com/vivider/p/3664020.html
