记录编号	78448	评测结果	AAAAAAAAAA
题目名称	棋盘游戏	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.069 s
提交时间	2013-11-03 22:07:40	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<deque>
#include<set>
using namespace std;
//二进制右起第i位表示右起第i位,从1开始计数
//认为0,1分别代表白,黑,空格是-1
/*
搜索顺序为:
左隔一格的棋子->左面棋子->右面棋子->右隔一格的棋子
*/
int pow2[30]={1};
int negpow2[30]={0};
int n;
class STATE{
public:
	int data;
	short space;//空格的位置
};
STATE ori,goal;
bool operator == (STATE a,STATE b){
	return a.data==b.data&&a.space==b.space;
}
bool operator < (STATE a,STATE b){
	if(a.data<b.data) return true;
	if(a.data>b.data) return false;
	if(a.space<b.space) return true;
	return false;
}
int getdig(int x,int k){//x的第k位
	return int((x&pow2[k-1])!=0);
}
vector<pair<STATE,int> > Q;
void output(int x){
	deque<int> ans;
	while(x){
		ans.push_front(Q[x].first.space);
		x=Q[x].second;
	}
	int i;
	for(i=1;i<=ans.size();i++){
		printf("%d ",2*n+2-ans[i-1]);
		if(i%20==0) printf("\n");
	}
	printf("\n");
}
int change(int x,int a,int b){
	int p=getdig(x,a),q=getdig(x,b);
	x&=negpow2[a-1],x&=negpow2[b-1];
	x|=(q<<(a-1)),x|=(p<<(b-1));
	return x;
}
int tot=0;
set<STATE> hash;
bool exist(STATE &x){
	return hash.find(x)!=hash.end();
}
void BFS(void){
	STATE now,temp;
	int l1,l2,r1,r2;
	while(tot<Q.size()){
		now=Q[tot].first;
		if(now.space<2*n+1) l1=getdig(now.data,now.space+1);
		if(now.space<2*n) l2=getdig(now.data,now.space+2);
		if(now.space<2*n&&l1!=l2&&l2==0){//左面隔一格的棋子过来
			temp.space=now.space+2;
			temp.data=change(now.data,now.space,now.space+2);
			if(!exist(temp)){
				Q.push_back(make_pair(temp,tot));
				hash.insert(temp);
				if(temp==goal){
					output(Q.size()-1);
					return;
				}
			}
		}
		if(now.space<2*n+1&&l1==0){//左面的棋子过来
			temp.space=now.space+1;
			temp.data=change(now.data,now.space,now.space+1);
			if(!exist(temp)){
				Q.push_back(make_pair(temp,tot));
				hash.insert(temp);
				if(temp==goal){
					output(Q.size()-1);
					return;
				}
			}
		}
		if(now.space>1) r1=getdig(now.data,now.space-1);
		if(now.space>2) r2=getdig(now.data,now.space-2);
		if(now.space>1&&r1==1){//右面的棋子过来
			temp.space=now.space-1;
			temp.data=change(now.data,now.space,now.space-1);
			if(!exist(temp)){
				Q.push_back(make_pair(temp,tot));
				hash.insert(temp);
				if(temp==goal){
					output(Q.size()-1);
				return;
				}
			}
		}
		if(now.space>2&&r1!=r2&&r2==1){//右面隔一格的棋子跳过来
			temp.space=now.space-2;
			temp.data=change(now.data,now.space,now.space-2);
			if(!exist(temp)){
				Q.push_back(make_pair(temp,tot));
				hash.insert(temp);
				if(temp==goal){
				output(Q.size()-1);
					return;
				}
			}
		}
		tot++;
	}
}
void work(void){
	Q.push_back(make_pair(ori,-1));
	BFS();
}
void init(void){
	scanf("%d",&n);
	int i;
	int temp;
	for(i=1;i<=26;i++) pow2[i]=pow2[i-1]*2;
	temp=0;
	for(i=0;i<2*n+1;i++) temp+=pow2[i];
	for(i=0;i<2*n+1;i++) negpow2[i]=temp&(~pow2[i]);
	temp=0;
	for(i=1;i<=n;i++) temp+=pow2[i-1];
	ori.data=temp,ori.space=n+1;
	temp=0;
	for(i=n+2;i<=2*n+1;i++) temp+=pow2[i-1];
	goal.data=temp,goal.space=n+1;
}
int main(){
	freopen("shuttleus.in","r",stdin);
	freopen("shuttleus.out","w",stdout);
	init();
	work();
	return 0;
}