题目背景
高高的星空，簇簇闪耀的群星形态万千。一个星座(cluster)是一群连通的星组成的非空连通星系，这里的连通是指水平，垂直或者对角相邻的两个星星。一个星座不能是另一个更大星座的一部分， 星座可以相似(similar)。如果两个星座有相同的形状，而且包括相同数目的星体，那么不管其方向性如何，就算相似。一般而言，星座可能的方向有八个，如图1所示。
题目描述
夜空可以表示为一份天体图(sky map)，它是一个由字符0和1组成的二维矩阵，字符1表示所在的位置有一颗星；字符0表示该位置上是空的.给定一份天体图，用同一个小写英文标识(mark)相似的所有星座。相似的星座必须用相同的字母标识，不同的星座表示为不同的字母。标识一个星座，就是将其中各星体对应的字符1替换为相应的小写字母.
输入输出格式
输入格式：
文件的前两行分别记录了天体图的宽度W、深度H。而天体图则是由接下来的H行表示，每行包括W个字符. ……
输出格式：
输出文件记录了天体图与文件STARRY.IN相似，不同之处在于，各个星座按照“任务”中的要求进行了标识(mark)。
对于同一个输入文件，可能会有很多不同的标识，此时，输出字典序最小的标识。
输入输出样例
输入样例#1： 复制
23
15
10001000000000010000000
01111100011111000101101
01000000010001000111111
00000000010101000101111
00000111010001000000000
00001001011111000000000
10000001000000000000000
00101000000111110010000
00001000000100010011111
00000001110101010100010
00000100110100010000000
00010001110111110000000
00100001110000000100000
00001000100001000100101
00000001110001000111000输出样例#1： 复制
a000a0000000000b0000000
0aaaaa000ccccc000d0dd0d
0a0000000c000c000dddddd
000000000c0b0c000d0dddd
00000eee0c000c000000000
0000e00e0ccccc000000000
b000000e000000000000000
00b0f000000ccccc00a0000
0000f000000c000c00aaaaa
0000000ddd0c0b0c0a000a0
00000b00dd0c000c0000000
000g000ddd0ccccc0000000
00g0000ddd0000000e00000
0000b000d0000f000e00e0b
0000000ddd000f000eee000说明
在这种情况下，天体图是一个长23宽为15的二维矩阵。请注意这幅天体图是对应（corresponds to）下面这个矩阵的图像。
Starry-2.gif 图starry-2：天体图
这是上述输入实例的一个可能的结果。请注意，该输出文件对应于下面的天空景象。
数据范围
0 <= 星空的长和宽 <= 100
0 <= 星座个数 <= 500
0 <= 不相似的星座个数 <= 26
1 <= 每个星座中星星个数 <= 160
------------------------------------------------------------------------------------
今天A了一道提高加的题目，心里美啧啧！
好了，自恋完毕，发题解咯（对不起打pascal的人，本人打C++），这道题一看，纯暴力！于是，我拿起了拳套，对电脑一顿猛砸（我最不擅长搜索！）
注：这道题是很好的一道搜索题，题目地址，练一下
但是，以我死猪不怕开水烫的毅力，想出了正解，首先，是输入：
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++)
{
scanf("%s",st+1);
for(int j=1;j<=m;j++)
{
a[i][j]/*1或0*/=st[j]-'0';
if(a[i][j]==0)h[i][j]=true;/*判断这个点可不可以被搜索*/
}
}然后，到了找星座了，定义八个方向，然后bfs一遍，求出来了，（注：本人比较喜欢x为横坐标
）
当然，
有人会说，找完星座，是不是要排序一遍，保证字典序，其实，只要在循环上做文章就行啦！
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)/*一格一格判断，这样保证按字典序，不信大家试一下*/
{
if(h[i][j]==false && a[i][j]==1)/*必须为1的点且没有找过*/
{
bfs(i,j,++k/*申请一个新的编号并遍历*/);
b[k].fa=k;/*并查集，后面讲怎么利用*/
}
}
}bfs来一发
：
void bfs(int qx,int qy,int uk)
{
b[uk].len=head=1;tail=2;
list[head].x=b[uk].a[1].x=b[uk].min.x=b[uk].max.x=qx;
list[head].y=b[uk].a[1].y=b[uk].min.y=b[uk].max.y=qy;
ll[qx][qy]=uk;/*判断这个点归属哪个编号的星座*/
h[qx][qy]=true;/*循环前的初始化，这部分要重视，很容易出细节错误*/
while(head!=tail)
{
int x=list[head].x,y=list[head].y;
for(int i=0;i<=7;i++)/*八个方向*/
{
int tx=x+dx[i],ty=y+dy[i];
if(tx>0 && ty>0 && tx<=n && ty<=m && h[tx][ty]==false && a[tx][ty]==1)/*判断搜过没有*/
{
h[tx][ty]=true;
list[tail].x=tx;list[tail++].y=ty;
b[uk].a[++b[uk].len].x=tx;
b[uk].a[b[uk].len].y=ty;/*记录点*/
b[uk].min.x/*接下来四个点记录的是四个极点的坐标（我把星座当成在一个长方形里的一个图案）*/=mymin(b[uk].min.x,tx);
b[uk].min.y=mymin(b[uk].min.y,ty);
b[uk].max.x=mymax(b[uk].max.x,tx);
b[uk].max.y=mymax(b[uk].max.y,ty);
ll[tx][ty]=uk;/*找到后的一系列骚操作*/
}
}
head++;
}
sort(b[uk].a+1,b[uk].a+b[uk].len+1,cmp);/*排序，排序按横坐标从小到大，相等列坐标从小到大*/
}然后，到了找相同，顺时针旋转90度的公式：x1,y1（旋转前）,x2,y2（旋转后）（x表横坐标，y表列坐标）
x2=y1,y2=max.x（最大的横坐标！最小的为1）-x1+1
node right(node x)
{
int tx=x.max.x;
for(int i=1;i<=x.len;i++)
{
int oox=x.a[i].x,ooy=x.a[i].y;
x.a[i].x=ooy;
x.a[i].y=tx-oox+1;/*公式*/
}
swap(x.max.x,x.max.y);/*行列交换*/
sort(x.a+1,x.a+x.len+1,cmp);/*排序*/
return x;
}但是，我们要注意，判断是为了防止出错，我们要把图案所位于的最小长方形移动到左上角的位置（以1,1,为min.x,min.y）
具体如下：
node right(node x)
{
int tx=x.max.x;
for(int i=1;i<=x.len;i++)
{
int oox=x.a[i].x,ooy=x.a[i].y;
x.a[i].x=ooy;
x.a[i].y=tx-oox+1;/*公式*/
}
swap(x.max.x,x.max.y);/*行列交换*/
sort(x.a+1,x.a+x.len+1,cmp);/*排序*/
return x;
}还有水平翻转操作：
inline node fanzhuan(node x)
{
for(int i=1;i<=x.len;i++)x.a[i].y=x.max.y-x.a[i].y+1;
sort(x.a+1,x.a+x.len+1,cmp);
return x;
}判断：
inline bool pd(node x,node y)
{
for(int i=1;i<=x.len;i++)
{
if(x.a[i].x!=y.a[i].x || x.a[i].y!=y.a[i].y)return false;
}
return true;
}最后附上并查集！
int findfa(int x)
{
if(b[x].fa!=x)b[x].fa=findfa(b[x].fa);/*记录现在的父亲*/
return b[x].fa;
}所有的函数讲完了，就到的主函数
for(int i=1;i<k;i++)
{
for(int j=i+1;j<=k;j++)
{
if(b[i].len==b[j].len)/*星星数相同才可能相同*/
{
node st1=yuchu(b[i]);
node st2=yuchu(b[j]);/*预处理*/
if(pd(st1,st2)==true)
{
int tfa=findfa(j);
b[i].fa=b[j].fa;/*认祖先，由于循环，这个点肯定还没认祖先（不算认自己）*/
break;/*加了并查集的潇洒*/
}
node stl1=right(st1);//旋转
if(pd(stl1,st2)==true)
{
int tfa=findfa(j);
b[i].fa=b[j].fa;
break;
}
stl1=right(stl1);
if(pd(stl1,st2)==true)
{
int tfa=findfa(j);
b[i].fa=b[j].fa;
break;
}
stl1=right(stl1);
if(pd(stl1,st2)==true)
{
int tfa=findfa(j);
b[i].fa=b[j].fa;
break;
}
stl1=fanzhuan(st1);//翻转
if(pd(stl1,st2)==true)
{
int tfa=findfa(j);
b[i].fa=b[j].fa;
break;
}
stl1=right(stl1);
if(pd(stl1,st2)==true)
{
int tfa=findfa(j);
b[i].fa=b[j].fa;
break;
}
stl1=right(stl1);
if(pd(stl1,st2)==true)
{
int tfa=findfa(j);
b[i].fa=b[j].fa;
break;
}
stl1=right(stl1);
if(pd(stl1,st2)==true)
{
int tfa=findfa(j);
b[i].fa=b[j].fa;
break;
}
//到这代表他们两不适合
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]!=0)
{
int tx=findfa(ll[i][j]);
int ty=ll[i][j];
if(oo[tx]/*代表这个星座是否有字母*/==0)oo[tx]=oo[ty]=++bibi;/*给他们申请一个新的字母*/
else oo[ty]=oo[tx];
printf("%c",oo[ty]+'a'-1);
}
else printf("0");
}
printf("
");
}至此，这题就A了，哈哈哈哈哈，喜欢点个赞呗
注：上面的图片侵权抱歉！