【题目来源】
洛谷：P1259 黑白棋子的移动 - 洛谷 (luogu.com.cn)
【题目描述】
有 \(2n\) 个棋子排成一行，开始为位置白子全部在左边，黑子全部在右边，如下图为 \(n=5\) 的情况：
移动棋子的规则是：每次必须同时移动相邻的两个棋子，颜色不限，可以左移也可以右移到空位上去，但不能调换两个棋子的左右位置。每次移动必须跳过若干个棋子（不能平移），要求最后能移成黑白相间的一行棋子。如 \(n=5\) 时，成为：
任务：编程打印出移动过程。
【输入】
一个整数 \(n\)。
【输出】
若干行，表示初始状态和每次移动的状态，用 o 表示白子，* 表示黑子，- 表示空行。
【输入样例】
7
【输入样例】
ooooooo*******--
oooooo--******o*
oooooo******--o*
ooooo--*****o*o*
ooooo*****--o*o*
oooo--****o*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*
【解题思路】
【算法标签】
《洛谷 P1259 黑白棋子的移动》 #递归# #Special judge#
【代码详解】
#include <iostream>
using namespace std;int n; // 初始'o'和'*'的数量（各n个）
char a[205]; // 存储当前排列状态的数组
string b[4] = { // 预定义的4种特殊排列模式"ooo*o**--", "o--*o**oo", "o*o*o*--o", "--o*o*o*o"
};// 输出数组从l到r的部分
void shuchu(int l, int r)
{for (int i = l; i <= r; i++) cout << a[i];cout << endl;
}// 递归处理排列变换
void f(int step)
{// 终止条件：当step减到3时使用预定义模式if (step == 3) {for (int i = 0; i < 4; i++) {cout << b[i]; // 输出预定义模式shuchu(10, 2*n+2); // 输出剩余部分}return;}// 输出当前状态shuchu(1, 2*n+2);// 执行交换操作1：移动两个'o'到右侧swap(a[step], a[step*2+1]);swap(a[step+1], a[step*2+2]);shuchu(1, 2*n+2); // 输出交换后的状态// 执行交换操作2：移动两个'*'到左侧swap(a[step], a[step*2-1]);swap(a[step+1], a[step*2]);// 递归处理下一步f(step-1);
}int main()
{cin >> n;// 初始化数组：前n个'o'，接着n个'*'，最后两个'-'for (int i = 1; i <= n; i++) {a[i] = 'o';a[i+n] = '*';}a[2*n+1] = '-';a[2*n+2] = '-';// 从n开始递归处理f(n);return 0;
}
【运行结果】
7
ooooooo*******--
oooooo--******o*
oooooo******--o*
ooooo--*****o*o*
ooooo*****--o*o*
oooo--****o*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*