记录编号	35579	评测结果	AAAAAAAA
题目名称	分球	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.273 s
提交时间	2012-02-25 21:34:12	内存使用	83.23 MiB

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <fstream>
using namespace std;

ifstream fin("balls.in");
ofstream fout("balls.out");

typedef unsigned short int usint;

const int INF=100000000;
const int MAXN=16;
usint Ball[MAXN];
usint hash[5000001]={0};
int N;
int M;
int Head=0;
int Tail=0;

bool check(usint *str)
{
	int s=0;
	for(int i=1;i<=2*N;i++)
	{
		if(str[i]==2) break;
		if(str[i]==1)
			s++;
	}
	if(s==N-1)
		return true;
	return false;
}

void Print(usint *str)
{
	int tmp;
	for(int i=1;i<=2*N;i++)
	{
		tmp=str[i];
		if(tmp==1) fout<<"a";
		if(tmp==0) fout<<" ";
		if(tmp==2) fout<<"b";
	}
	fout<<endl;
}

int Hash(usint *str)
{
	int s=0;
	int j=1;
	for(int i=2*N;i>=1;i--)
	{
		if(str[i]==2)
			s+=j;
		else if(str[i]==0)
			s+=2*j;
		j*=3;
	}
	return s;
}

class QUEUE
{
public:
	usint ball[16];
    usint father;
	usint pos;
	usint step;
	void clear()
	{
		for(int i=0;i<=15;i++)
			ball[i]=0;
	}
};  
QUEUE Q[2000000]; 

usint Index[500000];
void Output(QUEUE x)
{
	
	usint top=0;
	usint p=x.father;
	while(p!=0)
	{
		top++;
		Index[top]=p;
		p=Q[p].father;
	}
	for(int i=top;i>=1;i--) 
	{
		fout<<Q[Index[i]].step<<" ";
		Print(Q[Index[i]].ball);
	}
	fout<<x.step<<" ";
	Print(x.ball);
}

void Push(QUEUE x)
{
	Tail++;
	Q[Tail]=x;
	hash[Hash(x.ball)]=1;
}

QUEUE Pop()
{
	Head++;
	return Q[Head];
}

void bfs()
{
	QUEUE tmp,nxt;
	tmp.clear();
	for(int i=1;i<=2*N;i++)
		tmp.ball[i]=Ball[i];
	tmp.father=0;
	tmp.step=0;
	for(int i=1;i<=2*N;i++)
	{
		if(Ball[i]==0)
		{
			tmp.pos=i;
			break;
		}
	}
	Push(tmp);
	
	bool flag=true;
	
	usint tp;
	while(Head!=Tail && flag)
	{
		tmp=Pop();
		tp=tmp.pos;
		for(int i=1;i<=2*N;i++)
		{
			if(tmp.ball[i]==0 || tmp.ball[i+1]==0)
				continue;
			nxt=tmp;
			nxt.father=Head;
			nxt.pos=i;
			nxt.ball[tp]=nxt.ball[i];
			nxt.ball[tp+1]=nxt.ball[i+1];
			nxt.ball[i]=0;
			nxt.ball[i+1]=0;
			nxt.step=tmp.step+1;
			if(check(nxt.ball))
			{
				Output(nxt);
				flag=false;
				return;
			}
			else
				if(hash[Hash(nxt.ball)]==0)
					Push(nxt);
		}
	}
	fout<<"NO SOLUTION"<<endl;
}

void init()
{
	fin>>M;
	for(int i=1;i<=M;i++)
	{
		Head=0;
		Tail=0;
		fin>>N;
		usint top=0;
		char c;
		while(top<2*N)
		{
			c=fin.get();
			if(c!='a' && c!='b' && c!=' ')
				continue;
			if(c=='a') Ball[++top]=1;
			if(c=='b') Ball[++top]=2;
			if(c==' ') Ball[++top]=0;
		}
		if(check(Ball))  {fout<<"0 ";Print(Ball);continue;}
		
		for(int i=0;i<=5000000;i++)
			hash[i]=0;
		bfs();
		if(i<M)
			fout<<endl;
	}
}

int main()
{
	init();
	return 0;
}