【题目描述】

有2n个棋子（n≥4）排成一行，开始位置为白子全部在左边，黑子全部在右边，如下图为n=5的情形：○○○○○●●●●●

移动棋子的规则是：每次必须同时移动相邻的两个棋子，颜色不限，可以左移也可以右移到空位上去，但不能调换两个棋子的左右位置。每次移动必须跳过若干个棋子（不能平移），要求最后能移成黑白相间的一行棋子。

如n=5时，成为：○●○●○●○●○●

任务：编程打印出移动过程。

【输入描述】

输入n。

【输出描述】

移动过程。

【样例输入】

7

【样例输出】

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*
step10:o*o*o*--o*o*o*o*
step11:--o*o*o*o*o*o*o*

【题目分析】

观察样例： 

乍一看没啥规律，但是如果你仔细观察，可能会发现，样例中的第三行，是这样的：

oooooo******--o*

可以看到，前面一部分形成了六白六黑两个空的情形。这不就是n=6的情况吗？

再往下两行（样例中的第五行）则是这样的：

ooooo*****--o*o*

没错，前面又形成了n=5的情况。

再往下两行呢？（样例中的第七行）：

oooo****--o*o*o*

前面又形成了n=4的情况。

而题目中的数据范围是4≤n≤100，也就是n最小取4。

那么我们就差不多明白了，这是一道分治，不断的分解情况，将n=k的情况转化为n=k?1的情况，一直到n=4。

那么这是怎么转化的呢？还是一样观察样例，我们看看是怎么从n=7的情况转化为n=6的情况的。

ooooooo*******--      
        ||     ||
oooooo--******o*      
	||    ||
oooooo******--o*

看起来是把前边的中间的一黑一白移到最后的两个空位，然后再将原来排列的最后两颗星星补上前面的空位。（移动的部分已经用||标出。）

那么n=6或者n=5呢

oooooo******--o*
     ||     ||
ooooo--*****o*o*
     ||   ||
ooooo*****--o*o*

没错，还是这个套路。

转化的方法我们知道了，那么接下来再看$n=4$是怎么处理的吧。

oooo****--o*o*o*   
	||   ||
ooo--***o*o*o*o*   
	||  ||
ooo*o**--*o*o*o* 
	 ||    ||
o--*o**oo*o*o*o* 
	||   ||
o*o*o*--o*o*o*o*
	||    ||
--o*o*o*o*o*o*o*

这个看起来没什么规律，应该是$\mathrm{<span\; style="font-size:\; 14px;"></span>}$$\mathrm{<span\; style="font-size:\; 14px;">n</span>}<span\; style="font-size:\; 14px;">=</span>\mathrm{<span\; style="font-size:\; 14px;">4</span>}$的基本情况了。在代码中我们直接按照这种方法，照葫芦画瓢式移动就行。

【参考代码】

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 105;
int n;
char s[maxn * 2 + 5];
int empty_idx;//empty_idx记录的是两个空位中的前面那个空位的下标。

void print() {//输出函数
	for(int i = 1; i <= 2 * n + 2; i++)
		cout << s[i];
	cout <<  endl;
	return ;
}

void init() {//初始化函数
	for(int i = 1; i <= n; i++) 
		s[i] = 'o';
	for(int i = n + 1; i <= 2 * n; i++) 
		s[i] = '*';
	for(int i = 2 * n + 1; i <= 2 * n + 2; i++) 
		s[i] = '-';
	empty_idx = 2 * n + 1;
	print();//别忘了最初情况也需要输出
	return ;
}

void move(int x) {//移动函数
	s[empty_idx] = s[x];
	s[empty_idx + 1] = s[x + 1];
	s[x] = s[x + 1] = '-';
	empty_idx = x;
	print();
}
//move(x)的效果：将第x个棋与第x + 1个棋一起分别移到两个空位上

void solve(int k) {//分治函数
	if(k == 4) {
		move(4);
		move(8);
		move(2);
		move(7);
		move(1);
		//k=4的情况就是完全照葫芦画瓢咯。
	} else {
		move(k);//先把中间的移最后
		move(2 * k - 1);//再移后边的两个*移中间
		solve(k - 1);//分治
	}
}

int main() {
	cin >> n;//读入
	init();//初始化
	solve(n);//调用分治
	return 0;
}