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