ac1210.pas

这是在网络上搜集到的在东京大学的ACM上面解决的一些题目的源码

program tju1210;
const
  fac:array[1..5]of byte=(1,2,6,24,120);
type
  perm=array[1..6]of byte;
var
  a,b:perm;
  q:array[1..176]of record p:perm;reach,step:byte;last:boolean;
    end;
  v:array[1..720,1..5,boolean]of boolean;
  f,r,i,j,t,ans:word;
  c:char;
function id(p:perm):word;
  var
    i,j:byte;
  begin
    id:=1;
    for i:=1 to 5 do begin
      inc(id,fac[6-i]*(p[i]-1));
      for j:=i+1 to 5 do
        if p[j]>p[i] then dec(p[j]);
    end;
  end;
procedure add(a:perm;b:byte;c:boolean;d:byte);
  var
    x:word;
  begin
    x:=id(a);
    if v[x,b,c] then exit;
    inc(r);
    with q[r] do begin
      p:=a;reach:=b;last:=c;step:=d+1;
    end;
    v[x,b,c]:=true;
  end;
begin
  f:=0;r:=1;
  with q[1] do begin
    for i:=1 to 6 do p[i]:=i;
    reach:=1;last:=false;
    v[1,reach,last]:=true;
  end;
  repeat
    inc(f);
    with q[f] do begin
      //Right
      if reach<5 then
        add(p,reach+1,last,step)
      else if not last then
        add(p,5,true,step);
      //Swap0
      if reach>1 then begin
        t:=p[1];p[1]:=p[reach];p[reach]:=t;
        add(p,reach,last,step);
        t:=p[1];p[1]:=p[reach];p[reach]:=t;
      end;
      //Swap1
      if not last then begin
        t:=p[6];p[6]:=p[reach];p[reach]:=t;
        add(p,reach,true,step);
        t:=p[6];p[6]:=p[reach];p[reach]:=t;
      end;
    end;
  until f=r;

  repeat
    for i:=1 to 6 do begin read(c);a[i]:=ord(c)-48;end;read(c);
    for i:=1 to 6 do begin read(c);b[i]:=ord(c)-48;end;readln;
    ans:=99;
    for i:=1 to r do
      with q[i] do begin
        if not last and (b[6]<>a[p[6]]) then continue;
        t:=0;
        for j:=reach+1 to 5 do if b[j]<>a[p[j]] then begin t:=1;break;end;
        if t=1 then continue;
        t:=step;
        if last then inc(t,abs(b[6]-a[p[6]]));
        for j:=1 to reach do
          inc(t,abs(b[j]-a[p[j]]));
        if t<ans then ans:=t;
      end;
    writeln(ans);
  until seekeof;
end.