【数据结构•hash表】烦恼的设计师(SGOI)

【数据结构•hash表】烦恼的设计师(SGOI)

暂无测试数据。

Description

  烦恼的设计师(来自SGOI)
  春天到了,百花齐放,西湖公园里新设置了许多花坛,设计师想用不同的花摆出不同的图案以吸引游人,于是设计了各种图案并且在花圃中选好了要摆放的花。不幸的是负责搬运和摆放的工人因为临时有事,只将花放到花架上就匆匆离开了,并没有按照设计师原来的设计方案摆放,结果花坛杂乱不堪,设计师只好自己来调整花的位置。由于设计师通常从事脑力劳动,较少从事搬运和摆放花盆的体力工作,所以请你帮忙找出一种移动方法使工作量最小。
  不同种类的花有不同的类型编号,虽然地球上花的种类很多,但因为公园里的花不超过1,000,000种,所以花的类型编号不超过1,000,000。另一方面,出于美学考虑,一个花坛里摆放的不同种类的花不超过3种,且不同种类的花的数量不可太接近,对于任意两种花,数量多的花的盆数至少是数量少的花的2倍。
  花坛是正六边形的,共摆放有19盆花,每盆花都放在一个转盘上,转动一盆花下面的转盘,会使周围的6盆花顺时针或逆时针移动一个位置(但不可把花转到花坛外),称为一次操作。你的任务:用最少的操作使花坛由初始状态转化为符合设计图纸的目标状态。例如:
MvuSTe.png

Input

  输入文件共11行,1至5行描述花坛的初始状态,7至11行表示花盆应摆放的位置。中间以空行分隔,5行数字分别表示花坛的5个行,其中第1、5两行有3个整数,第2、4两行有4个整数,第3行有5个整数,表示每一行的花的类型,不同的数代表不同种类的花。

Output

  输出文件,一行,包含一个整数,即最少的操作数,数据保证20步之内有解。

Sample Input

1 1 1
1 2 1 1
1 1 1 1 1
1 1 1 1
1 1 1

1 1 1
1 1 1 1
1 1 2 1 1
1 1 1 1
1 1 1

Sample Output

1

Limitation

1s, 65536KiB for each test case.

Hint

题意描述:
  给定两个正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。于是我们将每一个状态与一个整数对应起来,使用除余法就可以了。

Source

GZOJ 1542

信息

ID
1034
难度
(无)
分类
(无)
标签
(无)
递交数
0
已通过
0
通过率
?
上传者