4.4.1 Shuttle Puzzle 棋盘游戏

题目描述:

大小为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个数(除了最后一行)。

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

样例输入:

3

样例输出:

3 5 6 4 2 1 3 5 7 6 4 2 3 5 4

时间限制: 1000ms
空间限制: 64MB

---

来源: USACO4-高级算法