记录编号	7889	评测结果	AAAAAATTAA
题目名称	移动骷髅	最终得分	80
用户昵称	苏轼	是否通过	未通过
代码语言	Pascal	运行时间	2.558 s
提交时间	2008-11-12 11:38:00	内存使用	5.45 MiB

program cch(input,output);
type
 ch=array[1..5,1..5] of integer;
 rp=record
     sz:ch;
     k:longint;
    end;
var
 s:array[1..100000] of rp;
 i,j,k,n,head,tail,code:longint;
 a,tmp:ch;
 x:char;

function check(a:ch):boolean;
var
 i,j,k:longint;
 flag:boolean;
begin
 for i:=1 to tail do
  begin
   flag:=true;
   for j:=1 to 5 do
    for k:=1 to 5 do
     if s[i].sz[j,k]<>a[j,k] then flag:=false;
   if flag then exit(false);
  end;
 exit(true);
end;

function bfs(a:ch):longint;
var
 i,j,tmpk:longint;
begin
 head:=1; tail:=1;
 s[head].sz:=a; s[head].k:=0;
 repeat
  for i:=1 to 5 do
   for j:=1 to 5 do
    if (s[head].sz[i,j]=1)or(s[head].sz[i,j]=2) then
     begin
      tmp:=s[head].sz; tmp[i,j]:=0;
      for k:=i+1 to 5 do
       if (tmp[k,j]=1)or(tmp[k,j]=2) then
        begin
         tmp[k-1,j]:=s[head].sz[i,j]; tmpk:=s[head].k+1;
         if tmp[3,3]=2 then exit(tmpk);
         if check(tmp) then
          begin
           inc(tail); s[tail].sz:=tmp; s[tail].k:=tmpk;
          end;
         break;
        end;
      tmp:=s[head].sz; tmp[i,j]:=0;
      for k:=i-1 downto 1 do
       if (tmp[k,j]=1)or(tmp[k,j]=2) then
        begin
         tmp[k+1,j]:=s[head].sz[i,j]; tmpk:=s[head].k+1;
         if tmp[3,3]=2 then exit(tmpk);
         if check(tmp) then
          begin
           inc(tail); s[tail].sz:=tmp; s[tail].k:=tmpk;
          end;
         break;
        end;
      tmp:=s[head].sz; tmp[i,j]:=0;
      for k:=j+1 to 5 do
       if (tmp[i,k]=1)or(tmp[i,k]=2) then
        begin
         tmp[i,k-1]:=s[head].sz[i,j]; tmpk:=s[head].k+1;
         if tmp[3,3]=2 then exit(tmpk);
         if check(tmp) then
          begin
           inc(tail); s[tail].sz:=tmp; s[tail].k:=tmpk;
          end;
         break;
        end;
      tmp:=s[head].sz; tmp[i,j]:=0;
      for k:=j-1 downto 1 do
       if (tmp[i,k]=1)or(tmp[i,k]=2) then
        begin
         tmp[i,k+1]:=s[head].sz[i,j]; tmpk:=s[head].k+1;
         if tmp[3,3]=2 then exit(tmpk);
         if check(tmp) then
          begin
           inc(tail); s[tail].sz:=tmp; s[tail].k:=tmpk;
          end;
         break;
       end;
   end;
  inc(head);
 until head>tail;
end;

begin
 assign(input,'klgame.in');
 assign(output,'klgame.out');
 reset(input);
 rewrite(output);
 readln(n);
 for i:=1 to n do
  begin
   for j:=1 to 5 do
    begin
     for k:=1 to 5 do
      begin
       read(x);
       val(x,a[j,k],code);
      end;
     readln;
    end;
   writeln('level ',i,':');
   writeln(bfs(a));
   readln;
  end;
 close(input);
 close(output);
end.