P2739 [USACO4.4]棋盘游戏Shuttle Puzzle

    • 207通过
    • 463提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签
  • 难度 普及+/提高
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    大小为3的棋盘游戏里有3个白色棋子,3个黑色棋子,和一个有7个格子一线排开的木盒子。3个白棋子被放在一头,3个黑棋子被放在另一头,中间的格子空着。

    初始状态: WWW_BBB

    目标状态: BBB_WWW

    在这个游戏里有两种移动方法是允许的:

    你可以把一个棋子移到与它相邻的空格;

    你可以把一个棋子跳过一个(仅一个)与它不同色的棋子到达空格。

    大小为N的棋盘游戏包括N个白棋子,N个黑棋子,还有有2N+1个格子的木盒子。

    这里是3-棋盘游戏的解,包括初始状态,中间状态和目标状态:

    WWW BBB

    WW WBBB

    WWBW BB

    WWBWB B

    WWB BWB

    W BWBWB

    WBWBWB BW WBWB

    BWBW WB

    BWBWBW BWBWB W

    BWB BWW

    B BWBWW

    BB WBWW

    BBBW WW

    BBB WWW

    请编一个程序解大小为N的棋盘游戏(1 <= N <= 12)。要求用最少的移动步数实现。

    输入输出格式

    输入格式:

    一个整数N。

    输出格式:

    输出用移动的棋子在棋盘的位置(位置从左到右依次为1, 2, ..., 2N+1)表示的变换序列,每个数字之间以空格分隔,每行20个数(除了最后一行)。

    输出的解还应当有最小的字典顺序(即如果有多组移动步数最小的解,输出第一个数最小的解;如果还有多组,输出第二个数最小的解;...)。

    输入输出样例

    输入样例#1: 复制
    3
    输出样例#1: 复制
    3 5 6 4 2 1 3 5 7 6 4 2 3 5 4

    说明

    题目翻译来自NOCOW。

    USACO Training Section 4.3

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。