洛谷-P1259 黑白棋子的移动（基础分治）

题目描述

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

○○○○○●●●●●

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

○●○●○●○●○●

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

输入格式

一个整数n(n<=100)

输出格式

若干行，表示初始状态和每次移动的状态，用"o"表示白子，"*"表示黑子，"-"表示空行。

输入输出样例

输入 #1

7

输出 #1

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*

---

#include <bits/stdc++.h>

using namespace std;

vector<char> seq(210);

int n;
int step = 0; //记录到了第几步
int pos; //记录空位的起始位置

void print()
{
    //setiosflags(ios::right);
    //cout << "step" << setw(2) << step << ":";
    for (int i = 1; i <= 2 * n + 2; ++i) cout << seq[i];
    cout << endl;
    ++step;
}

void init(int n)
{
    pos = 2 * n + 1;
    for (int i = 1; i <= n; ++i) seq[i] = 'o';
    for (int i = n + 1; i <= 2 * n; ++i) seq[i] = '*';
    seq[2 * n + 1] = seq[2 * n + 2] = '-';
    print();
}

void move(int k)
{
    std::swap(seq[k], seq[pos]);
    std::swap(seq[k + 1], seq[pos + 1]);
    pos = k;
    print();
}


void solve(int n)
{
    if (n == 4) {
        move(4); move(8); move(2); move(7); move(1);
    }
    else {
        move(n); move(2 * n - 1); solve(n - 1);
    }
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    init(n);
    solve(n);

    return 0;
}

解析：首先分析n = 4的时候如何移动。（注--表示空位）

​ ○○○○●●●●--

第一步：○○○--●●●○●

第二步：○○○●○●●--●

第三步：○--●○●●○○●

第四步：○●○●○●--○●

第五步：--○●○●○●○●

如果n = 5的时候，分析：

​ ○○○○○●●●●●--

第一步：○○○○--●●●●○●

第二步：○○○○●●●●--○●

发现序列的前半部分恰好是n = 4的情况，于是发现n的移动可以在n-1的移动基础上构造。