解题思路

2n 个棋子排成一行，白子（o）在左、黑子（*）在右，每次把相邻的两个棋子整体移动到空位，目标是排成黑白相间。这是一个经典的递归问题。

找规律：

从 oooo...oooo****...***-- 开始，每两轮可以把最右边的一对 o 固定住：

1. 先把第 k 个 o 和它右边的 （即 o 对）移到最右边的空位
2. 再把中间的 ** 移到新空位

这样最右边就固定了一对 o*，剩下的棋子继续重复。

具体移动规则（用初始位置编号）：

• 主循环：k 从 n 递减到 5，每次移动位置 (k-1,k) 的 o* 和位置 (2k-2,2k-1) 的 **
• 最后处理剩余的固定 5 步，把前面剩下的棋子也排成交替

把每一步移动后的棋盘输出出来，就是完整的移动过程。

参考代码

#include <iostream>
#include <string>
using namespace std;

int main() {
    int n;
    cin >> n;

    string a = string(n, 'o') + string(n, '*') + "--";
    int e = 2 * n;
    int cnt = 1;

    cout << "step0:" << a << endl;

    // 移动 (p,q) 位置的棋子到空位 (e,e+1)
    auto mv = [&](int p, int q) {
        a[e] = a[p];
        a[e + 1] = a[q];
        a[p] = '-';
        a[q] = '-';
        e = p;
        cout << "step" << cnt++ << ":" << a << endl;
    };

    // 主循环：每轮固定一对，交替移动
    for (int k = n; k >= 5; k--) {
        mv(k - 1, k);              // 移动 o* 对
        mv(2 * k - 2, 2 * k - 1);  // 移动 ** 对
    }

    // 最后的特例步骤
    mv(3, 4);          // 最后一对 o*
    mv(7, 8);          // 移动 *o
    mv(1, 2);          // 移动 oo
    mv(6, 7);          // 移动 *o
    mv(0, 1);          // 移动 o*

    return 0;
}

复杂度分析

• 时间复杂度：O(N²)，每步输出棋盘长度为 2n
• 空间复杂度：O(N)，一个字符串存棋盘