「fjWC2015」当小威遇上棋盘

2015年2月4日2,7406

「题目描述」

一个井字形棋盘,上面有24个格子(如下图)。这些格子上面有1,2,3三种数字, 且每种数字有 8 格。一开始,这些格子上的数字是随机分布的。你的任务是移动这些格 子使得中间 8 个格子的数字相同。有 8 种移动方式,分别标记为 A 到 H,可以理解为 拉动 4 条链,如图的变换为“AC”。问至少需要多少次拉动,才能从初始状态到达目标 状态?(保证数据有解)

「输入格式」

从 jing.in 中输入数据

有多组数据。每组数据一行,24 个数字,从上到下从左到右表示棋盘上的数字。以 0 结束数据。

「输出格式」

输出到 jing.out 中 每组数据一行,输出最少移动次数。

「样例输入」

111132323132231222312133 111111112222222233333333 0

「样例输出」

2 4

「样例说明」

第一个数据变换为“AC”。 第二个数据变换为“DDHH”。

「数据规模与约定」

对于 30% 的数据,最大移动次数 ≤ 9,数据组数 ≤ 10。 对于 60% 的数据,最大移动次数 ≤ 12,数据组数 ≤ 20。 对于 100% 的数据,最大移动次数 ≤ 12,数据组数 ≤ 30。

题解

迭代深搜

加上剪枝和估价函数就能过了

对于每个局面计算至少还要多少步能使得中间8个相同

 

说点什么

提醒
avatar
zld3794955

123不是等价的么,因此对123直接暴力BFS一遍不就好了。。这样状态数不到750000种,并且答案完全可以预处理。。QAQ

LXX
LXX

小威是您吗QAQ