【fjwc2015】当小威遇上棋盘

2015年2月4日2,1746

【题目描述】

一个井字形棋盘,上面有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个相同

 

  • LXX2015年2月5日 下午6:37 回复

    小威是您吗QAQ

    #1  
    • hzwer2015年2月5日 下午6:56 回复
      admin

      这我不知道啊有可能

      #11
      • 杀人鬼城2015年2月5日 下午8:57 回复

        居然没人发现那天的提交记录里就有个小威吗_(:з」∠)_

        #12
        • hzwer2015年2月5日 下午9:16 回复
          admin

          我看到了TAT

          #13
          • lin_toto2015年2月6日 上午10:31

            那是我们干的

            #14
  • zld37949552015年3月19日 下午11:33 回复

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

    #2