题目背景
《爱与愁的故事第三弹·shopping》第二章。
题目描述
爱与愁大神在这家目标店买了2x份礼物，打算分给班级同学。其中有x份黑礼品，x份白礼品，2x+2个空礼盒。一开始这2x份礼品排成一行放在左边2x个空礼盒上，黑礼品在左边，白礼品在右边，最右边有两个空礼盒。现在爱与愁大神要把这2x个礼品移成黑白相间的一排。他正无聊着，于是定了个规矩：每次必须同时移动相邻的两个礼品，颜色不限，可以左移也可以右移到空礼盒上去，但不能调换两个礼品的左右位置。每次移动必须跳过若干个礼盒（不能平移），最后弄成黑白相间的一行礼品。这个规矩却难倒了自己，你能帮爱与愁大神出出主意吗？
输入格式
只有1行：x
输出格式
若干行：
第i行为步骤i-2（1代表黑礼品，2代表白礼品，0代表空礼盒）。注意step 0不计入总数。
最后1行为总数。
输入输出样例
输入 #1
7
输出 #1
Step 0:1111111222222200 Step 1:1111110022222212 Step 2:1111112222220012 Step 3:1111100222221212 Step 4:1111122222001212 Step 5:1111002222121212 Step 6:1111222200121212 Step 7:1110022212121212 Step 8:1112122002121212 Step 9:1002122112121212 Step 10:1212120012121212 Step 11:0012121212121212 11
说明/提示
40%数据：x<=10
100%数据：x<=70
思路
动手模拟 比如当n=4的时候应该怎么去移动
n=5时有些地方和 n=4一样 n=6时有些地方和 n=5 一样 n=7时有些地方和 n=6 一样 。。。。。。
我们就可以把n的问题分解成n-1的问题
代码
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=150;
char c[N];
int n,st,sp;
void print() {
printf("Step %d:",st);
for(int i=1; i<=2*n+2; i++)
printf("%c",c[i]);
printf("\n");
st++;
}
void move(int k) {
for(int j=0; j<=1; j++) {
c[sp+j]=c[k+j];
c[k+j]='0';
}
sp=k;
print();
}
void mv(int n) {
if(n==4) {
move(4),move(8);
move(2),move(7),move(1);
} else {
move(n);
move(2*n-1),mv(n-1);
}
}
int main () {
scanf("%d",&n);
st=0,sp=2*n+1;
for(int i=1; i<=n; i++)
c[i]='1';
for(int i=n+1; i<=2*n; i++)
c[i]='2';
c[2*n+1]='0',c[2*n+2]='0';
print();
mv(n);
printf("%d\n",st-1);
return 0;
}