ACM试题1175 Starry Night

《ACM试题1175 Starry Night》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、StarryNight00201066题意描述给定一张星云图，其中相邻的星星连成长星去，求出其中所有星云，并判断其中相似的星云。题意描述星云相似是指两个所包含星星个数相同的星云通过旋转和翻转能变的形状相同。图中给出了八种相似的情形。输入输入：星云图的长H和宽W，接着是星云图本身，用0表示该位置无星星，1表示有星星。输出如右图，将找到的星云用小写字母代替，相似的星云用相同的小写字母代替。不相似的星云按行列坐标从小到大的顺序依次与a到z对应。原图中的0不变。数据规模算法分析很明显题目包含两个任务。一.找所有的星云。二.判断两星云是

2、否相似。问题一十分典型，可以用广度优先的方法去解决，而问题二则需要判断是否相似，我们可以将所有已发现的互不相似的星云保存起来，每次找到一个新的星云就将它与已发现的互不相似的星云比较，判断是否相似。算法分析：1.找一个不属于任何一个已找到的星云的点。2.从这个点开发找一个新的星云。3.与以保存的星云比较，看是否相似。若不相似，则保存这个星云。子问题1的代码广度优先搜索voidfind(intx,inty){inthh,x1,y1,i;hh=-1;len=1;star[0][0]=x;star[0][1]=y;map[x][y]=

3、2;do{hh++;x=star[hh][0];y=star[hh][1];for(i=0;i<8;i++){x1=x+dir[i][0];y1=y+dir[i][1];if(x1<0

4、

5、y1<0

6、

7、x1>=h

8、

9、y1>=w)continue;if(map[x1][y1]!=1)continue;star[len][0]=x1;star[len][1]=y1;len++;map[x1][y1]=2;}}while(hh

10、uster;clusterlist数组保存所有不相似的星云。而clusterstar中保存当前发现的星云。2.与list[i]比较，若star.num不等于list[i].num则结束。3.分别对第i个星云进行8种变换，得到变换后的坐标，保存到clusterbak中。4.将坐标平移成正值（xj,yj)，1<=j<=star.num依次记bakmap[xj][yj]=1;5.将star的坐标移为正值（aj,bj)，依次判断bakmap[aj][bj]是否为1.若对某个j为0，则不相同。否则相同。6.8种方法均判断完后则可知是否相

11、似。总结：本题难度不大，而且容易调试，但上面判断相似的过程比较麻烦（与block类似），是否能进一步优化？谢谢大家！