记录编号	8091	评测结果	AAAAAAAAAA
题目名称	移动骷髅	最终得分	100
用户昵称	francis	是否通过	通过
代码语言	Pascal	运行时间	0.923 s
提交时间	2008-11-12 20:58:08	内存使用	3.64 MiB

program game;
const
fin='klgame.in';
fou='klgame.out';
g:array[1..4,1..2]of longint=((-1,0),(0,1),(1,0),(0,-1));
var
t:array[1..5,1..5]of longint;
d:array[1..100000,1..5,1..5]of byte;
a,l,r:array[1..100000]of longint;
p,q,deep,x,y,i,j,n,k:longint;
bo:boolean;
st:string;
f1,f2:text;

procedure init;
begin
assign(f1,fin);
assign(f2,fou);
reset(f1); rewrite(f2);
readln(f1,n);
end;

function num(i:longint):longint;
var
y,xx,p,q,k:longint;
begin
k:=25; xx:=0;
for p:=1 to 5 do
for q:=1 to 5 do
begin
 dec(k); y:=0;
 if d[i,p,q]=1 then y:=1;
 if d[i,p,q]=2 then y:=(p-1)*5+q;
 xx:=xx+trunc(exp(k*ln(2)))*y;
end;
exit(xx);
end;

procedure find(i,x:longint);
begin
if x=a[i] then begin bo:=true; exit; end;
if x<a[i] then
   if l[i]=0 then begin bo:=false; a[p]:=x; l[i]:=p; exit; end
             else find(l[i],x);
if x>a[i] then
   if r[i]=0 then begin bo:=false; a[p]:=x; r[i]:=p; exit; end
             else find(r[i],x);
end;

procedure print;
begin
writeln(f2,'level ',k,':');
writeln(f2,deep);
end;

procedure bfs(x,y:longint);
var
s,xx,yy,k,i,j,kk,ii,jj:longint;
begin
inc(deep);
for k:=x to y do
for i:=1 to 5 do
for j:=1 to 5 do
if (d[k,i,j]<>0)  then
for kk:=1 to 4 do
 begin
  s:=0; xx:=i; yy:=j;
  while (xx+g[kk,1]>0)and(xx+g[kk,1]<=5)and(yy+g[kk,2]>0)and(yy+g[kk,2]<=5)
         and(d[k,xx+g[kk,1],yy+g[kk,2]]=0) do
           begin
           xx:=xx+g[kk,1]; yy:=yy+g[kk,2];
           end;
  if (xx+g[kk,1]>0)and(xx+g[kk,1]<=5)and(yy+g[kk,2]>0)and(yy+g[kk,2]<=5) then
   begin
    inc(p);
    for ii:=1 to 5 do
    for jj:=1 to 5 do
    d[p,ii,jj]:=d[k,ii,jj];
    d[p,i,j]:=0; d[p,xx,yy]:=d[k,i,j];
    q:=num(p);
    if (xx=3)and(yy=3)and(d[k,i,j]=2) then begin print; exit; end;
    find(1,q);
    if bo=true then dec(p);
  end;
 end;
if p>=y+1 then bfs(y+1,p);
end;

procedure main;
begin
for k:=1 to n do
begin
 for i:=1 to 5 do
 begin
  readln(f1,st);
  for j:=1 to 5 do
  begin
    t[i,j]:=ord(st[j])-48;
    if t[i,j]=2 then begin x:=i; y:=j; end;
  end;
 end;
 readln(f1);
 deep:=0;
 if (x=3)and(y=3) then print;
 for i:=1 to 5 do
 for j:=1 to 5 do
 d[1,i,j]:=t[i,j];
 p:=1; q:=num(1);
 fillchar(l,sizeof(l),0);
 fillchar(r,sizeof(r),0);
 a[1]:=q;
 bfs(1,1);
end;  end;

begin
init;
main;
close(f1); close(f2);
end.