80 lines
2.2 KiB
C++
80 lines
2.2 KiB
C++
#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;
|
||
}
|