1164castle观察城堡地图统计_第1页
1164castle观察城堡地图统计_第2页
1164castle观察城堡地图统计_第3页
1164castle观察城堡地图统计_第4页
1164castle观察城堡地图统计_第5页
已阅读5页，还剩5页未读， 继续免费阅读

付费下载

下载本文档

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

文档简介

1、城堡要求：观察城堡地图，统计1、总共的房间数2、最大房间的面积竞赛书 P2IOI 1994 Day1 Problem 2Online Judge 1164分析统计问题，解题的关键在于：一、设计一种合理的数据结构描述问题二、统计效率问题描述定义：点： 城堡中的格直接连接：相邻且公共边非墙连接：直接连接或经由其他点直接连接房间：相互连接的若干点的集合房间的面积：房间中点的个数优点：1、每个点对应输入数据的一个数字2、直接连接可以根据一个点的状态计算出来不需要预处理统计算法：1、将所有点的状态标记为“未知”2、遍历所有点如果遇到的点为“未知”则将该点拓展为一个房间（拓展过程中会将拓展出的点标记为属于

2、相应的房间）拓展完成后进行相应的统计拓展算法：初始化：设置open、close两个空点集将种子置入open集计算：while(open非空)从open中取出一点a,置入close检查与a直接连接的点b(最多四个)if (b不属于open且b不属于close)then 将b置入open时间效率:每个点最多被访问5次：上下左右点的直接连接和主程序的遍历每次访问要检测是否属于open或close集所需时间为：O（城堡面积） (点集随机访问时间）每个点都进open、close集各一次，出open 集一次，所需时间为O（城堡面积）*（点集顺序访问时间）所以总的时间效率为：O（城堡面积）*（点集顺序访问时间+点集随机访问时间）注：我用的点集实现了常数级的两种访问（见代码）空间效率每个点的描述 O（城堡面积）每个点的状态 O（城堡面积）Open、Close 两集合o（城堡面积）总的空间效率O（城堡面积）技巧：Close集不用保存，因为一

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

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

最新文档

评论

0/150

提交评论