TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3235
  • 题目
  • P3235移棋游戏 pro
    限制 : 时间限制 : - MS   空间限制 : 262144 KB  SPJ
    评测说明 : 1s,256MB
    问题描述

    本题为NKOJ1083的数据范围升级版
    有$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*

    提示

    数据范围
    \(n\le 16\)


    来源  感谢nodgd