下载此文档

1513 烦恼的设计师(来自SGOI).doc


文档分类:资格/认证考试 | 页数:约6页 举报非法文档有奖
1/6
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/6 下载此文档
文档列表 文档介绍
【数据结构•hash表】烦恼的设计师(SGOI)TimeLimit:10000MS MemoryLimit:65536KTotalSubmit:epted:18Description 烦恼的设计师(来自SGOI) 春天到了,百花齐放,西湖公园里新设置了许多花坛,设计师想用不同的花摆出不同的图案以吸引游人,于是设计了各种图案并且在花圃中选好了要摆放的花。不幸的是负责搬运和摆放的工人因为临时有事,只将花放到花架上就匆匆离开了,并没有按照设计师原来的设计方案摆放,结果花坛杂乱不堪,设计师只好自己来调整花的位置。由于设计师通常从事脑力劳动,较少从事搬运和摆放花盆的体力工作,所以请你帮忙找出一种移动方法使工作量最小。不同种类的花有不同的类型编号,虽然地球上花的种类很多,但因为公园里的花不超过1,000,000种,所以花的类型编号不超过1,000,000。另一方面,出于美学考虑,一个花坛里摆放的不同种类的花不超过3种,且不同种类的花的数量不可太接近,对于任意两种花,数量多的花的盆数至少是数量少的花的2倍。花坛是正六边形的,共摆放有19盆花,每盆花都放在一个转盘上,转动一盆花下面的转盘,会使周围的6盆花顺时针或逆时针移动一个位置(但不可把花转到花坛外),称为一次操作。你的任务:用最少的操作使花坛由初始状态转化为符合设计图纸的目标状态。例如: 初始状态目标状态如图,只需将处于圆心位置的那盆花的转盘顺时针转动一个位置,红色的花就移动到了目标位置。Input 输入文件共11行,1至5行描述花坛的初始状态,7至11行表示花盆应摆放的位置。中间以空行分隔,5行数字分别表示花坛的5个行,其中第1、5两行有3个整数,第2、4两行有4个整数,第3行有5个整数,表示每一行的花的类型,不同的数代表不同种类的花。Output 输出文件,一行,包含一个整数,即最少的操作数,数据保证20步之内有解。SampleInput111121111111111111111111111**********SampleOutput1Hint题意描述: 给定两个正6边形的花坛,要求求出从第一个变化到第二个的最小操作次数以及操作方式。一次操作是:选定不在边上的一盆花,将这盆花周围的6盆花按照顺时针或者逆时针的顺序依次移动一个单位。限定一个花坛里摆放的不同种类的花不超过3种,对于任意两种花,数量多的花的盆数至少是数量少的花的2倍。(这是SGOI-8的一道题)解题分析: 首先确定本题可以用广度优先搜索处理,然后来看问题的规模。正6边形共有19个格子可以用来放花,而且根据最后一句限定条件,至多只能存在C(2,19)*C(5,17)=1058148种状态,用搜索完全可行。然而操作的时候,可以预料产生的重复节点是相当多的,需要迅速判重才能在限定时间内出解,因此想到了哈希表。那么这个哈希函数如何设计呢?注意到19个格子组成6边形是有顺序的,而且每一个格子只有3种可能情况,那么用3进制19位数最大3^20-1=3486784400,注意,这个数值大于2^31,但小于2^32。于是我们将每一个状态与一个整数对应起来,使用除余法就可以了。Sourceprogramflowers;constsize=1058148;base=262143;circle:array[1..7,1..6]ofinteger=((1,2,6,10

1513 烦恼的设计师(来自SGOI) 来自淘豆网www.taodocs.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数6
  • 收藏数0 收藏
  • 顶次数0
  • 上传人cjc201601
  • 文件大小40 KB
  • 时间2020-08-11