2120: Shuttle Puzzle
Memory Limit:125 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
## 题目描述
大小为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