ac1139.pas

某牛人写的acm.tongji.edu.cn上大部分ac的代码,仅供学习研究,请不要用来作弊

program tju1139;
const
  maxstate=1062599;
var
  c:array[0..24,0..4]of longint;
  a:array[0..5]of byte;
  q:array[-1..maxstate]of longint;
  step:array[-1..maxstate]of shortint;
  n,t,i,j,k,x,s,f,r:longint;
  ch:char;
  found:boolean;
procedure map2state;
  var
    i,j,p:byte;
  begin
    for i:=1 to 4 do
      for j:=i+1 to 5 do
        if a[i]>a[j] then begin
          p:=a[i];a[i]:=a[j];a[j]:=p;
        end;
    s:=0;p:=1;
    for i:=0 to 24 do
      if i=a[p] then
        if p=5 then break else inc(p)
      else
        inc(s,c[24-i,5-p]);
    s:=s*20+a[0];
    for i:=1 to 5 do
      if a[i]<a[0] then dec(s) else break;
  end;
procedure state2map;
  var
    i,p:byte;
  begin
    a[0]:=s mod 20;s:=s div 20;p:=1;
    for i:=0 to 24 do
      if s<c[24-i,5-p] then begin
        a[p]:=i;inc(p);if p>5 then break;
      end
      else
        dec(s,c[24-i,5-p]);
    for i:=1 to 5 do
      if a[i]<=a[0] then inc(a[0]);
  end;
procedure add;
  begin
    map2state;
    if step[s]=127 then begin
      inc(r);q[r]:=s;step[s]:=step[q[f]]+1;
      if a[0]=12 then found:=true;
    end;
  end;
begin
  for i:=0 to 24 do begin
    c[i,0]:=1;
    for j:=1 to 4 do
      if j>i then break else c[i,j]:=c[i,j-1]*(i+1-j) div j;
  end;

  readln(n);
  for t:=1 to n do begin
    x:=0;
    for i:=0 to 4 do begin
      for j:=0 to 4 do begin
        read(ch);
        case ch of
          '1':begin inc(x);a[x]:=i*5+j;end;
          '2':a[0]:=i*5+j;
        end;
      end;
      readln;
    end;
    if t<n then readln;

    fillchar(step,sizeof(step),127);
    found:=false;
    f:=-1;q[-1]:=-1;step[-1]:=-1;r:=-1;add;
    while not found do begin
      inc(f);
      for i:=0 to 5 do begin
        for j:=0 to 5 do
          if (i<>j) then begin
            s:=q[f];state2map;
            if (a[i] div 5=a[j] div 5) and (abs(a[i]-a[j])>1) then begin
              x:=1;
              for k:=0 to 5 do
                if (a[k] div 5=a[i] div 5) and ((a[k]-a[i])*(a[k]-a[j])<0) then begin
                  x:=0;break;
                end;
              if x=1 then begin
                x:=a[i];
                if a[i]<a[j] then a[i]:=a[j]-1 else a[i]:=a[j]+1;
                add;
              end;
            end
            else if (a[i] mod 5=a[j] mod 5) and (abs(a[i]-a[j])>5) then begin
              x:=1;
              for k:=0 to 5 do
                if (a[k] mod 5=a[i] mod 5) and ((a[k]-a[i])*(a[k]-a[j])<0) then begin
                  x:=0;break;
                end;
              if x=1 then begin
                x:=a[i];
                if a[i]<a[j] then a[i]:=a[j]-5 else a[i]:=a[j]+5;
                add;
              end;
            end;
            if found then break;
          end;
          if found then break;
        end;
    end;
    writeln('level ',t,':');
    writeln(step[q[r]]);
  end;
end.