【9702】黑白棋的移动

Time Limit: 3 second
Memory Limit: 2 MB

【问题描述】

    有2n个棋子(n≥4)排成一行，开始位置为白子全部在左边，黑子全部在右边，如下图为n=5的情形：
    ○○○○○●●●●●
    移动棋子的规则是：每次必须同时移动相邻的两个棋子，颜色不限，可以左移也可以右移到空位上去，但不能调换两个棋子的左右位置。每次移动必须跳过若干个棋子（不能平移），要求最后能移成黑白相间的一行棋子。如n=5时，成为：
    ○●○●○●○●○●
    任务：编程打印出移动过程。

【输入格式】

1行。n的值

【输出格式】

不定行，每行输出“step +称动的步数:黑白棋子及空位的分布情况”（即移动过程），用字母“o”表示白棋，用“*”表示黑棋，用“-”（连接符横杠）表示空位。

【输入样例】

【输出样例】

    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*

【题解】
对于n=5的情况。
ooooo*****--
我们把5,6移到空位。
oooo--****o*
然后把靠后的连续两个*移到空位；
oooo****--o*
对。1-10又变成n=4的情况了。
然后n=6也可以按照上面的方法转换成n=5的情况。然后再转换成n=4的情况。
以此类推。
然后n=4要怎么放呢？
样例有啊！自己看嘛！
【代码】
#include <cstdio>
#include <iostream>

char s[50];
int n,pkongge,ans = -1;

void input_data()
{
	scanf("%d", &n);//输入n
	pkongge = 2 * n + 1;//然后记录空格的位置。
}

void pri()//打印答案。
{
	ans++;//递增答案
	printf("step %d:", ans);
	for (int i = 1; i <= 2 * n + 2; i++) //一位位地输出。
		putchar(s[i]);
	printf("
");
}


void init() //初始化。
{ //1-n放o，n+1-2*n放* ,2*n+1-2*n+2是空格。
	for (int i = 1; i <= n; i++)
		s[i] = 'o';
	for (int i = n + 1; i <= 2 * n; i++)
		s[i] = '*';
	s[2 * n + 1] = '-';
	s[2 * n + 2] = '-';
	pri();//打印答案。这是步骤0；
}

void swap (char &a, char &b) //交换两个字符。
{
	char t;
	t = a;
	a = b;
	b = t;
}

void move(int p)//把p移到空格，p+1移到空格+1；
{
	swap(s[p], s[pkongge]);
	swap(s[p + 1], s[pkongge + 1]);
	pkongge = p; //记录空格新的位置
	pri(); //打印答案。
}

void mov(int k) //移n=k时的方法。
{
	if (k == 4) //如果k==4了则按照样例输出里n==4的方法移动。
	{
		move(4); move(8); move(2); move(7); move(1);
	}
	else //否则把两个棋子移开。然后变成k-1的移法。
	{
		move(k);
		move(k * 2 - 1);
		mov(k - 1);
	}
}

void get_ans()
{
	mov(n);
	//system("pause"); 不要加上这一句！！！！！！！
}

int main()
{
	input_data();
	init();
	get_ans();
	return 0;
}