USACO Starry Night

本题的思路很直接：先找出所有的cluster，然后逐一判断是否相似，若相似则合并。
用到了DFS和并查集。
其中比较难处理的是判断两个cluster是否相似，本人采用的是模拟旋转和对称，然后用memcmp比较的方法。USACO给出的代码里貌似用到了二分查找，本人还没有看懂。

在NOCOW上看到一个更简便的判断相似的方法：在cluster的面积和星星数相同的情况下，如果所有前一个cluster中星星两两之间的距离和等于后一个中星星两两之间的距离和，那么它们是相似的。不知这种方法是否存在漏洞。
不过USACO给的测试数据太弱了，前面4个点都是可以用数星星数+算面积直接通过。

C语言: 高亮代码由发芽网提供

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004
005 struct rect
006 {
007     int imin,imax,jmin,jmax;
008 }range[501];   //boundary of clusters
009
010 _Bool havestar[101][101];
011 char assign[510];  //cluster # to letter
012 int cluster[101][101];   //[x][y] in what cluster
013 int H,W;
014 int ccnt = 0;
015 int dcnt = 0;
016 int x[8] = {0,0,-1,-1,-1,1,1,1};
017 int y[8] = {1,-1,1,-1,0,0,-1,1};
018 int starcnt[510];    //star num in a cluster
019 int father[510];    //disjoint set
020
021 void init()
022 {
023     int i,j;
024     char map[101][101];
025     scanf("%d%d\n",&W,&H);
026     for(i = 0;i < H;i ++)
027         scanf("%s\n",map[i]);
028     for(i = 0;i < H;i ++)
029         for(j = 0;j < W;j ++)
030         {
031             cluster[i][j] = -1;   //belong to no cluster
032             if(map[i][j] == '1')    havestar[i][j] = 1;
033             else havestar[i][j] = 0;
034         }
035 }
036
037 _Bool visit[101][101];
038 void mark_cluster(int i,int j,int d)  //DFS marking clusters
039 {
040     int k;
041     if(visit[i][j])    return;
042     if(havestar[i][j] == 0)    return;
043     if(i < 0 || i >= H)    return;
044     if(j < 0 || j >= W)    return;
045     visit[i][j] = 1;
046     cluster[i][j] = d;
047     //update range
048     if(i < range[d].imin)    range[d].imin = i;
049     else if(i > range[d].imax)    range[d].imax = i;
050     if(j < range[d].jmin)    range[d].jmin = j;
051     else if(j > range[d].jmax)    range[d].jmax = j;
052     //go around
053     for(k = 0;k < 8;k ++)
054         mark_cluster(i + x[k],j + y[k],d);
055 }
056
057 int get(int a)
058 {
059     if(father[a] == a)    return a;
060     else    father[a] = get(father[a]);
061     return father[a];
062 }
063
064 void merge(int a,int b)
065 {
066     father[get(a)] = father[get(b)];
067 }
068
069 int cover(int a)
070 {
071     return (range[a].imax - range[a].imin) * (range[a].jmax - range[a].jmin);
072 }
073
074 void rotate(_Bool dest[][101],_Bool src[][101],int li,int lj)   //90 degrees clockwise
075 {
076     int i,j;
077     for(i = 0;i <= li;i ++)
078         for(j = 0;j <= lj;j ++)
079             dest[j][li - i] = src[i][j];
080 }
081
082 void mirror(_Bool dest[][101],_Bool src[][101],int li,int lj)    //horizontal mirror
083 {
084     int i,j;
085     for(i = 0;i <= li;i ++)
086         for(j = 0;j <= lj;j ++)
087             dest[i][lj - j] = src[i][j];
088 }
089
090 void copyrange(_Bool dest[][101],int num)
091 {
092     int i,j;
093     for(i = range[num].imin;i <= range[num].imax;i ++)
094         for(j = range[num].jmin;j <= range[num].jmax;j ++)
095             if(cluster[i][j] == num)
096                 dest[i - range[num].imin][j - range[num].jmin] = havestar[i][j];
097 }
098
099 int similar(int a,int b)
100 {
101     static _Bool ta[101][101],tb1[101][101],img[101][101],tb2[101][101];
102     if(starcnt[a] != starcnt[b])    return 0;
103     if(cover(a) != cover(b))    return 0;
104     //////
105     memset(ta,0,sizeof(ta));memset(tb1,0,sizeof(tb1));
106     copyrange(ta,a);copyrange(tb1,b);
107     if(memcmp(ta,tb1,sizeof(ta)) == 0)    return 1;
108     memset(img,0,sizeof(img));
109     mirror(img,tb1,range[b].imax - range[b].imin,range[b].jmax - range[b].jmin);
110     if(memcmp(ta,img,sizeof(ta)) == 0)    return 1;
111     //////
112     memset(tb2,0,sizeof(tb2));
113     rotate(tb2,tb1,range[b].imax - range[b].imin,range[b].jmax - range[b].jmin);
114     memcpy(tb1,tb2,sizeof(tb1));
115     if(memcmp(ta,tb1,sizeof(ta)) == 0)    return 1;
116     memset(img,0,sizeof(img));
117     mirror(img,tb1,range[b].jmax - range[b].jmin,range[b].imax - range[b].imin);
118     if(memcmp(ta,img,sizeof(ta)) == 0)    return 1;
119     //////
120     memset(tb2,0,sizeof(tb2));
121     rotate(tb2,tb1,range[b].jmax - range[b].jmin,range[b].imax - range[b].imin);
122     memcpy(tb1,tb2,sizeof(tb1));
123     if(memcmp(ta,tb1,sizeof(ta)) == 0)    return 1;
124     memset(img,0,sizeof(img));
125     mirror(img,tb1,range[b].imax - range[b].imin,range[b].jmax - range[b].jmin);
126     if(memcmp(ta,img,sizeof(ta)) == 0)    return 1;
127     //////
128     memset(tb2,0,sizeof(tb2));
129     rotate(tb2,tb1,range[b].imax - range[b].imin,range[b].jmax - range[b].jmin);
130     memcpy(tb1,tb2,sizeof(tb1));
131     if(memcmp(ta,tb1,sizeof(ta)) == 0)    return 1;
132     memset(img,0,sizeof(img));
133     mirror(img,tb1,range[b].jmax - range[b].jmin,range[b].imax - range[b].imin);
134     if(memcmp(ta,img,sizeof(ta)) == 0)    return 1;
135     return 0;
136 }
137
138 void pt()
139 {
140     int i,j;
141     for(i = 0;i < H;i ++)
142     {
143         for(j = 0;j < W;j ++)
144         {
145             if(havestar[i][j])    printf("%c",assign[get(cluster[i][j])]);
146             else printf("0");
147         }
148         printf("\n");
149     }
150 }
151
152 int main()
153 {
154     freopen("starry.in","r",stdin);
155     freopen("starry.out","w",stdout);
156     int i,j;
157     init();
158     //mark all clusters
159     for(i = 0;i < H;i ++)
160         for(j = 0;j < W;j ++)
161             if(havestar[i][j] && cluster[i][j] == -1)
162             {
163                 range[ccnt].imin = range[ccnt].imax = i;
164                 range[ccnt].jmin = range[ccnt].jmax = j;
165                 mark_cluster(i,j,ccnt);
166                 ccnt ++;
167             }
168     //count stars in each cluster
169     memset(starcnt,0,sizeof(starcnt));
170     for(i = 0;i < H;i ++)
171         for(j = 0;j < W;j ++)
172             if(havestar[i][j])    starcnt[cluster[i][j]] ++;
173     //init disjoint set
174     for(i = 0;i < ccnt;i ++)
175         father[i] = i;
176     //merge similar clusters
177     for(i = 0;i < ccnt;i ++)
178         for(j = i + 1;j < ccnt;j ++)
179         {
180             if(get(i) != get(j) && similar(i,j))    merge(i,j);
181         }
182     //assignment
183     memset(assign,0,sizeof(assign));
184     for(i = 0;i < H;i ++)
185         for(j = 0;j < W;j ++)
186         {
187             if(havestar[i][j] && assign[get(cluster[i][j])] == 0)    //haven't assigned yet
188                 assign[get(cluster[i][j])] = (char)('a' + dcnt ++);
189         }
190     pt();
191     fclose(stdin);
192     fclose(stdout);
193     return 0;
194 }