记录编号	41717	评测结果	AAAAAAAAAA
题目名称	移动骷髅	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.020 s
提交时间	2012-08-10 12:12:21	内存使用	0.31 MiB

#include <cstdio>
#include <cstdlib>
#include <queue>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
int T,ans;
typedef vector<char> klmap;
typedef vector<int> Hash;
map<Hash,int> hash;
int binary[26];

class Queue
{
public:
	int f;klmap sta;
	inline void read()
	{
		sta.clear();int c;f=1;sta.push_back(0);
		for(int i=1;i<=5;i++)
		{
			for(int j=1;j<=5;j++)
			{
				c=0;while(c<'0' || c>'9')
				scanf("%c",&c);sta.push_back(c);
			}
		}
	}
	vector<int> gethash()
	{
		vector<int> tmp; 
		tmp.push_back(0);
		tmp.push_back(0);
		for(int i=1;i<=25;i++)
		{
			if(sta[i]=='2') tmp[1]=i;
			else tmp[0]=tmp[0]+(sta[i]-'0')*binary[i];
		}
		return tmp;
	}
}Haji;

Queue tmp,nxt;
klmap ts,ns;
queue<Queue> q;

inline int Min(int a,int b) {return a<b?a:b;}

inline void debug(klmap k)
{
	for(int i=1;i<=5;i++)
	{
		for(int j=1;j<=5;j++)
			printf("%c",k[(i-1)*5+j]);
		printf("\n");
	}
	printf("\n");
}

inline void bfs()
{
	q.push(Haji);int tf,nf,nh;
	hash[Haji.gethash()]=1;
	int now,step[5]={0,1,-1,5,-5};
	while(q.size())
	{
		tmp=q.front(); q.pop(); ts=tmp.sta; tf=tmp.f;
		if(tf+1>=ans) continue;
		for(int i=1;i<=25;i++)
		{
			if(ts[i]=='0') continue;
			for(int k=1;k<=4;k++)
			{
				if(tf+1>=ans) continue;
				now=i; while(1)
				{
					now+=step[k];
					if(now<1 || now>25 || (now%5==0 && step[k]==-1) || (now%5==1 && step[k]==1))
						goto end;
					if(ts[now]>'0') break;
				}
				now-=step[k];
				if(now==i) continue;
				ns=ts; ns[now]=ns[i]; ns[i]='0'; nf=tf+1;
				if(ns[13]=='2') {/*debug(ts);debug(ns);*/ ans=Min(ans,nf);continue;}
				nxt.sta=ns; nxt.f=nf; nh=hash[nxt.gethash()]; 
				if(nh!=0 && nh<=nf) continue;
				hash[nxt.gethash()]=nf; q.push(nxt);
				end:;
			}
		}
	}
}

int main()
{
	freopen("klgame.in","r",stdin);
	freopen("klgame.out","w",stdout);
	binary[1]=1;for(int i=2;i<=25;i++)
		binary[i]=binary[i-1]*2;
	scanf("%d\n",&T);
	for(int i=1;i<=T;i++)
	{
		Haji.read();
		hash.clear();
		ans=100000000;
		bfs();
		printf("level %d:\n%d\n",i,ans-1);
	}
	return 0;
}