记录编号	8018	评测结果	AAAAAAAAAA
题目名称	移动骷髅	最终得分	100
用户昵称	zqzas	是否通过	通过
代码语言	C++	运行时间	0.464 s
提交时间	2008-11-12 18:02:20	内存使用	15.52 MiB

#include <iostream>

#define MAXN 10
#define MAXLONG 1000000
#define INF 999999999

using namespace std;

const int n=5;
const int Dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int u,ans,start,start_x,start_y,que_x[MAXLONG],que_y[MAXLONG],que[MAXLONG],deep[MAXLONG];

inline int getNum(int a,int x,int y)
{
	if (  (a & (1<< (x*n+y)) )==(1<< (x*n+y)) )
		return 1;
	else
		return 0;
}

inline void makeZero(int &a,int x,int y)
{
	a-=1<<(x*n+y);
}

inline void makeOne(int &a,int x,int y)
{
	a+=1<<(x*n+y);
}

inline bool judge(int tail)
{
	int i;
	for (i=0;i<tail;i++)
		if (que[i]==que[tail] && que_x[i]==que_x[tail] && que_y[i]==que_y[tail])
			return false;
	return true;
}

void bfs()
{
	int a,k,i,j,d,x,y,zan,head=-1,tail=0;
	que[0]=start;
	que_x[0]=start_x;
	que_y[0]=start_y;
	deep[0]=0;
	while (head<tail)
	{
		zan=a=que[++head];
		for (k=0;k<n*n;k++)
		{
			if ((a & (1<<k))!=(1<<k))
				continue;
			i=k/n;
			j=k%n;
			for (d=0;d<4;d++)
			{
				a=zan;
				x=i;
				y=j;
				while (1)
				{
					x=x+Dir[d][0];
					y=y+Dir[d][1];
					if (!(x>=0 && x<n && y>=0 && y<n))
						break;
					if ( getNum(a,x,y)==1)
					{
						if (getNum(a,x-Dir[d][0],y-Dir[d][1])==0)
						{
							makeOne(a,x-Dir[d][0],y-Dir[d][1]);
							makeZero(a,i,j);
							tail++;
							que[tail]=a;
							deep[tail]=deep[head]+1;
							if (i==que_x[head] && j==que_y[head])
							{
								que_x[tail]=x-Dir[d][0];
								que_y[tail]=y-Dir[d][1];
							}
							else
							{
								que_x[tail]=que_x[head];
								que_y[tail]=que_y[head];
							}
							if (!judge(tail))
								tail--;
							if (que_x[tail]==2 && que_y[tail]==2)
							{
								ans=deep[tail];
								return;
							}							
						}
						break;
					}
				}
			}

		}
	}
}

void run()
{
	ans=INF;
	bfs();
}

void ini()
{
	int p,i,j;
	char c;
	cin>>u;
	for (p=1;p<=u;p++)
	{
		start=0;
		for (i=0;i<n;i++)
			for (j=0;j<n;j++)
			{
				cin>>c;
				if (c!='0')
					start+=1<<(i*n+j);
				if (c=='2')
				{
					start_x=i;
					start_y=j;
				}
			}
		run();
		cout<<"level "<<p<<':'<<endl;
		cout<<ans;
		if (p!=u)
			cout<<endl;
		memset(que,0,sizeof(que));
		memset(deep,0,sizeof(deep));
		memset(que_x,0,sizeof(que_x));
		memset(que_y,0,sizeof(que_y));
	}
	
}

int main()
{
	freopen("klgame.in","r",stdin);
	freopen("klgame.out","w",stdout);
	ini();
	return 0;
}