2020.6.8
T1 棋子移动
题面
类似于洛谷p1259, 但是这次要输出每一次移动的方案而不是状态。
输入一个n, 代表有2n个棋子, 输出方案的每一步. (n>=4)
输入
4
输出
4,5-->9,10
8,9-->4,5
2,3-->8,9
7,8-->2,3
1,2-->7,8
样例解释
ooooxxxx__
ooo__xxxox
oooxoxx__x
o__xoxxoox
oxoxox__ox
__oxoxoxox
题解
举个例子
n=5时
oooooxxxxx__
如果这时将5,6拿走, 再把9,10拿回来
oooo__xxxxox
ooooxxxx__ox
那么这时就把问题转换成n=4时的子问题了
这样对于每一个大于4的n, 都能通过n*2次操作转化为n=4的情况并且可以直接输出n=4的样例输出。
这样就可以写出非常简单的代码
#include<iostream>
#include<cstdio>
using namespace std;
int n;
int main(){
//freopen("piece.in","r",stdin);
//freopen("piece.out","w",stdout);
cin>>n;
for(int i=n;i>4;i--){//将问题变成n-1的子问题
cout<<i<<","<<i+1<<"-->"<<i*2+1<<","<<i*2+2<<endl;
cout<<i*2-1<<","<<i*2<<"-->"<<i<<","<<i+1<<endl;
}
cout<<"4,5-->9,10"<<endl;//直接输出n=4的子问题方案（边界）
cout<<"8,9-->4,5"<<endl;
cout<<"2,3-->8,9"<<endl;
cout<<"7,8-->2,3"<<endl;
cout<<"1,2-->7,8"<<endl;
//fclose(stdin);
//fclose(stdout);
return 0;
}