python/TangDou/XiTi/1308.cpp

#include <bits/stdc++.h>

using namespace std;

//n：几个空心的圆
//sp:空格开始的位置索引
int n, sp, st = 0;

//用来模拟的字符数组
char c[101];

//打印
void print() {
    int i;
    cout << "step " << st << ":";
    for (i = 1; i <= 2 * n + 2; i++) cout << c[i];//进行输出
    cout << endl;
    st++;
}

//移动一步
void move(int k) {
    int j;
    for (j = 0; j <= 1; j++) { //循环两次，一次移动两个
        c[sp + j] = c[k + j];
        c[k + j] = '-';
    }
    sp = k;
    //输出
    print();
}

//主要过程
void mv(int n) {
    //n等于4的情况要特殊处理
    if (n == 4) {
        move(4);
        move(8);
        move(2);
        move(7);
        move(1);
        //以上是人为观察出来的死的步骤，真也太扯了吧,是人能想出的招吗？这和分治有啥关系，Shit~
    } else {
        /*
        当n>4时，移动2次可以转换成n−1的情况，转换到n=4时直接暴力输出移动路线，然后递归回去即可，据此容易想到总移动步数为(n−4)×2+5。
        经过对题目的观察，发现题目规律，当n>4时，总是将中间的一对两个不同的棋子移到最右边的空位，然后再把最右边的一对黑棋子移到先前的空位上，如此往复，
        直到剩下四对黑白棋没有移动。不过我们发现，这4对棋子的移法是一成不变的，不受其他棋子影响。因此，这个条件就可以作为递归边界，得出最后5步的走法。
         */
        move(n);                    //将中间的一对两个不同的棋子移到最右边的空位
        move(2 * n - 1);         //再把最右边的黑棋子移到先前的空位上
        //转化为子问题
        mv(n - 1);
    }
}

int main() {
    //输入+输出重定向
    freopen("../1308.txt", "r", stdin);

    cin >> n;
    //初始化
    int i;
    sp = 2 * n + 1;
    for (i = 1; i <= n; i++) c[i] = 'o';
    for (i = n + 1; i <= 2 * n; i++) c[i] = '*';
    c[2 * n + 1] = '-';
    c[2 * n + 2] = '-';

    //输出原始的形态
    print();

    //mv函数调用，包含输出
    mv(n);

    //关闭文件
    fclose(stdin);

    return 0;
}