【题解】黑白棋子移动
【题目描述】
有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*
没错，还是这个套路。
转化的方法我们知道了，那么接下来再看是怎么处理的吧。
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*
这个看起来没什么规律，应该是的基本情况了。在代码中我们直接按照这种方法，照葫芦画瓢式移动就行。
【参考代码】
#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;
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。
