棋盘游戏(Shuttle Puzzle)
   

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

　　初始状态: WWW_BBB
　　目标状态: BBB_WWW

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

　　1. 你可以把一个棋子移到与它相邻的空格；
　　2. 你可以把一个棋子跳过一个(仅一个)与它不同色的棋子到达空格。

　　大小为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)。要求用最少的移动步数实现。

　　程序名字: shuttle

　　输入格式

　　一个整数N。

　　范例输入(文件shuttle.in)

　　3

　　输出格式

　　用空格在棋盘的位置(位置从左到右依次为1, 2, ..., 2N+1)表示棋盘的状态。输出棋盘的状态变换序列，每行20个数(除了最后一行)。
　　输出的解还应当有最小的字典顺序(即如果有多组移动步数最小的解，输出第一个数最小的解；如果还有多组，输出第二个数最小的解；...)。

　　范例输出(文件shuttle.out)

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


    

 
网站导航 | 关于曙光 | 联系我们 | 请提意见
Copyright © FuJian Sunshine Educational Info. Co.,Ltd.
福建曙光教育资讯有限公司 版权所有