TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P1083
  • 問題
  • P1083移棋游戏
    制限 : 時間制限 : - MS   メモリ制限 : 262144 KB  SPJ
    問題説明

    有$2n(n\ge 4)$个棋子排成一行,开始时白子全在左边,黑子全在右边,最右边有两个空格:

    OOOO****__
    

    要求把它移成白黑(左白右黑)相间的一行棋子(左侧两个空位):

    __O*O*O*O*
    

    移动规则是:每次必须同时移动相邻的2个棋子,颜色不限。不能调换这2个棋子的左右位置。移动必须跳过至少1个棋子到左边或右边的空位上去,不能平移。

    找出一种步数最少的移动步骤!

    入力形式

    一个整数$n$

    出力形式

    初始到目标的所有步骤,具体看样例。

    サンプル入力

    4

    サンプル出力

    step 0:OOOO****__
    step 1:OOO__***O*
    step 2:OOO*O**__*
    step 3:O__*O**OO*
    step 4:O*O*O*__O*
    step 5:__O*O*O*O*

    ヒント

    空位用下划线“_”表示,表示白子的“O”为大写字母“呕”

    P.S.
    这个题的原题是个错题。原为vijos上题,命题者原本意图是用分治法,将规模为$n$的问题转化为规模为$n-1$的问题求出解,原题$n\le100$。但实际上这种做法是错误的,因为这样求出的移动方案不是最优方案。最优方案对任意的$n\ge4$只需要$n+1$步,也就是输出$n+2$行,但分治需要的$2n-3$步。
    本题输入数据中$n\le8$,用搜索+减枝可依通过。nodgd试了一下,搜索写得比较好的情况下可以过$n\le30$的数据。


    ソース  感谢nodgd填补陈年老坑,提供SPJ