记录编号	7883	评测结果	AAAAAAAAAA
题目名称	移动骷髅	最终得分	100
用户昵称	BYVoid	是否通过	通过
代码语言	C++	运行时间	0.044 s
提交时间	2008-11-12 11:36:26	内存使用	0.26 MiB

#include <iostream>

using namespace std;

class MC
{
public:
	int pos[25];
	int cnt;
};

int compare(const MC &a,const MC &p)
{
	int i;
	if (a.cnt==-1)
		return -1;
	if (p.cnt==-1)
		return 1;
	for (i=0;i<a.cnt;i++)
	{
		if (a.pos[i]<p.pos[i])
			return -1;
		if (a.pos[i]>p.pos[i])
			return 1;
	}
	return 0;
}
inline bool operator <= (MC& a,MC& p)
{
	int c=compare(a,p);
	return c==-1 || c==0;
}

struct point
{
	int x,y;
};

struct Map
{
	int step;
	point s[25];
};

class tQueue
{
public:
	class linklist
	{
	public:
		linklist* next;
		Map value;
		linklist()
		{
			next=0;
		}
	};
	linklist *first,*last;
	int size;
	void ins(Map &p)
	{
		if (size==0)
			first=last=new linklist;
		else
			last=last->next=new linklist;
		last->value=p;
		size++;
	}
	Map pop()
	{
		Map rtn=first->value;
		linklist *tfirst=first;
		first=first->next;
		delete tfirst;
		size--;
		return rtn;
	}
	void reset()
	{
		while(size) pop();
		first=last=0;
	}
	tQueue()
	{
		size=0;
		first=last=0;
	}
}; 

class tNode
{
	public:
		tNode *left,*right;
		int fix,cnt;
		MC v;
		tNode(MC tv,tNode *N) :v(tv),left(N),right(N)
		{
			cnt=1;
			fix=rand();
		}
};

class tTreap
{
	private:
		void rot_r(tNode *&p)
		{
			tNode *q=p->left;
			int tcnt=p->cnt;
			p->cnt=q->right->cnt+p->right->cnt+1;
			q->cnt=tcnt;

			p->left=q->right;
			q->right=p;
			p=q;
		}
		void rot_l(tNode *&p)
		{
			tNode *q=p->right;
			int tcnt=p->cnt;
			p->cnt=q->left->cnt+p->left->cnt+1;
			q->cnt=tcnt;

			p->right=q->left;
			q->left=p;
			p=q;
		}
		void _ins(tNode *&p,const MC& v)
		{
			if (p==Null)
			{
				p=new tNode(v,Null);
			}
			else
			{
				p->cnt++;
				if (compare(v,p->v)==-1)
				{
					_ins(p->left,v);
					if (p->left->fix < p->fix)
						rot_r(p);
				}
				else
				{
					_ins(p->right,v);
					if (p->right->fix < p->fix)
						rot_l(p);
				}
			}
		}


		bool _find(tNode *p,const MC &v)
		{
			if (p==Null)
			   return false;
			int c=compare(v,p->v);
			if (c==0)
				return true;
			if (c==-1)
			{
				return _find(p->left,v);
			}
			else
			{
				return _find(p->right,v);
			}
		}
		void _clear(tNode *p)
		{
			if (!p || p==Null)
				return;
			_clear(p->left);
			_clear(p->right);
			delete p;
		}

	public:
		tNode *root,*Null,*ptr;
		MC P;
		tTreap()
		{
			P.cnt=-1;
			root=Null=new tNode(P,0);
			Null->cnt=0;
			Null->fix=0x7FFFFFFF;
		}
		void ins(MC v)
		{
			_ins(root,v);
		}
		bool find_value(MC v)
		{
			return _find(root,v);
		}
		void clear()
		{
			_clear(root);
			root=Null;
		}
};

int N,Cnt,Red,ctr;
int Hash[6][6];
Map S;
tQueue Q;
tTreap Treap;

MC encode(Map &p)
{
	MC T;
	int i,a;
	for (i=0;i<Cnt;i++)
	{
		a=(p.s[i].x-1)*5+p.s[i].y-1;
		T.pos[i]=a;
	}
	T.cnt=Cnt;
	return T;
}


int BFS()
{
	Map p,q;
	point t;
	int i,x,y;
	Q.ins(S);
	MC code;

	while (Q.size)
	{
		ctr++;
		p=Q.pop();
		q=p;
		code=encode(p);
		bool succ=Treap.find_value(code);
		if (succ)
		{
			continue;
		}
		Treap.ins(code);

		q.step++;
		for (i=0;i<Cnt;i++)
		{
			x=p.s[i].x;
			y=p.s[i].y;
			Hash[x][y]=ctr;
		}
		for (i=0;i<Cnt;i++)
		{
			//up
			for (x=p.s[i].x,y=p.s[i].y,x--;x>=1;x--)
			{
				if (Hash[x][y]==ctr)
				{
					x++;
					if (x!=p.s[i].x)
					{
						t=q.s[i];
						if (i==Red && x==3 && y==3) return q.step;
						q.s[i].x=x;
						q.s[i].y=y;
						Q.ins(q);
						q.s[i]=t;
					}
					break;
				}
			}
			//down
			for (x=p.s[i].x,y=p.s[i].y,x++;x<=5;x++)
			{
				if (Hash[x][y]==ctr)
				{
					x--;
					if (x!=p.s[i].x)
					{
						t=q.s[i];
						if (i==Red && x==3 && y==3) return q.step;
						q.s[i].x=x;
						q.s[i].y=y;
						Q.ins(q);
						q.s[i]=t;
					}
					break;
				}
			}
			//left
			for (x=p.s[i].x,y=p.s[i].y,y--;y>=1;y--)
			{
				if (Hash[x][y]==ctr)
				{
					y++;
					if (y!=p.s[i].y)
					{
						t=q.s[i];
						if (i==Red && x==3 && y==3) return q.step;
						q.s[i].x=x;
						q.s[i].y=y;
						Q.ins(q);
						q.s[i]=t;
					}
					break;
				}
			}
			//right
			for (x=p.s[i].x,y=p.s[i].y,y++;y<=5;y++)
			{
				if (Hash[x][y]==ctr)
				{
					y--;
					if (y!=p.s[i].y)
					{
						t=q.s[i];
						if (i==Red && x==3 && y==3) return q.step;
						q.s[i].x=x;
						q.s[i].y=y;
						Q.ins(q);
						q.s[i]=t;
					}
					break;
				}
			}
		}
	}
}

void init()
{
	int i,step;
	point p;
	char c;
	freopen("klgame.in","r",stdin);
	freopen("klgame.out","w",stdout);
	scanf("%d\n",&N);
	for (i=1;i<=N;i++)
	{
		Cnt=0;
		for (p.x=1;p.x<=5;p.x++)
		{
			for (p.y=1;p.y<=5;p.y++)
			{
				c=getchar();
				while (c==10 || c==13) c=getchar();
				if (c=='2' || c=='1')
				{
					if (c=='2')
						Red=Cnt;
					S.s[ Cnt++ ]=p;
				}
			}
		}
		step=BFS();
		printf("level %d:\n%d\n",i,step);
		Q.reset();
		Treap.clear();
	}
}

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