ACM试题1175 Starry Night.ppt_第1页
ACM试题1175 Starry Night.ppt_第2页
ACM试题1175 Starry Night.ppt_第3页
ACM试题1175 Starry Night.ppt_第4页
ACM试题1175 Starry Night.ppt_第5页
已阅读5页，还剩7页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

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

2、先的方法去解决，而问题二则需要判断是否相似，我们可以将所有已发现的互不相似的星云保存起来，每次找到一个新的星云就将它与已发现的互不相似的星云比较，判断是否相似。,算法分析：,1.找一个不属于任何一个已找到的星云的点。 2.从这个点开发找一个新的星云。 3.与以保存的星云比较，看是否相似。若不相似，则保存这个星云。,子问题1的代码,广度优先搜索 void find (int x,int y) int hh,x1,y1,i; hh=-1; len=1; star00=x; star01=y; mapxy=2; do hh+; x=starhh0; y=starhh1; for (i=0;i=h|y

3、1=w) continue; if (mapx1y1!=1) continue; starlen0=x1; starlen1=y1; len+; mapx1y1=2; while (hhlen-1); ,子问题2,1.typedef struct int num; int unit1602; cluster; cluster list数组保存所有不相似的星云。 而cluster star中保存当前发现的星云。 2. 与listi比较，若star.num不等于listi.num则结束。 3. 分别对第i个星云进行8种变换，得到变换后的坐标，保存到cluster bak中。 4. 将坐标平移成正值（xj,yj)，1=j=star.num依次记bakmapxjyj=1; 5. 将star的坐标移为正值（aj,bj)，依次判断bakmapajbj是否为1.若对某个j为0，则不相同。否则相同。 6. 8种方法均判断完后则可知是否相似。,总结：,本题

人人文库> 全部分类> 生活休闲 > 科普知识

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论