#include 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; }