1773: 黑白棋子的移动（chessman）
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：4
Solved：2
Description
有2n个棋子（n≥4）排成一行，开始位置为白子全部在左边，黑子全部在右边，如下图为n=5的情形：
○○○○○●●●●●
移动棋子的规则是：每次必须同时移动相邻的两个棋子，颜色不限，可以左移也可以右移到空位上去，但不能调换两个棋子的左右位置。每次移动必须跳过若干个棋子（不能平移），要求最后能移成黑白相间的一行棋子。如n=5时，成为：
○●○●○●○●○●
任务：编程打印出移动过程。
○○○○○●●●●●
移动棋子的规则是：每次必须同时移动相邻的两个棋子，颜色不限，可以左移也可以右移到空位上去，但不能调换两个棋子的左右位置。每次移动必须跳过若干个棋子（不能平移），要求最后能移成黑白相间的一行棋子。如n=5时，成为：
○●○●○●○●○●
任务：编程打印出移动过程。
Input
一个数，输入n，为2n个棋子
Output
若干行
每行为移动步骤
Sample Input Copy
7Sample Output Copy
step 0:ooooooo*******--
step 1:oooooo--******o*
step 2:oooooo******--o*
step 3:ooooo--*****o*o*
step 4:ooooo*****--o*o*
step 5:oooo--****o*o*o*
step 6:oooo****--o*o*o*
step 7:ooo--***o*o*o*o*
step 8:ooo*o**--*o*o*o*
step 9:o--*o**oo*o*o*o*
step 10:o*o*o*--o*o*o*o*
step 11:--o*o*o*o*o*o*o*HINT
w【算法分析】
w
我们先从n=4开始试试看，初始时：
w ○○○○●●●●
w第1步：○○○——●●●○●
{—表示空位}
w第2步：○○○●○●●——●
w第3步：○——●○●●○○●
w第4步：○●○●○●——○●
w第5步：——○●○●○●○●
w 如果n=5呢？我们继续尝试，希望看出一些规律，初始时：
w ○○○○○●●●●●
w第1步：○○○○——●●●●○●
w第2步：○○○○●●●●——○●
w 这样，n=5的问题又分解成了n=4的情况，下面只要再做一下n=4的5个步骤就行了。同理，n=6的情况又可以分解成n=5的情况，……，所以，对于一个规模为n的问题，我们很容易地就把他分治成了规模为n-1的相同类型子问题。
w 数据结构如下：数组c[1..max]用来作为棋子移动的场所，初始时，c[1]~c[n]存放白子（用字符o表示），c[n+1]~c[2n]存放黑子（用字符*表示），c[2n+1]，c[2n+2]为空位置（用字符—表示）。最后结果在c[3]~c[2n+2]中。