ac1258.pas

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

{$Q-,R-}
program tju1258;
const
  move:array[1..2,0..8]of byte=((1,2,5,0,4,8,3,6,7),(0,1,2,4,5,3,6,7,8));
  fact:array[1..9]of longint=(1,2,6,24,120,720,5040,40320,362880);
  fact9=362880;
type
  board=array[0..8]of byte;
var
  q:array[0..fact9]of board;
  step:array[1..fact9]of byte;
  ans:array[0..fact9-1]of byte;
  a:board;
  f,r,m,i,t:longint;
function id(a:board):longint;
  var
    i,j:longint;
  begin
    id:=0;
    for i:=8 downto 1 do begin
      inc(id,a[i]*fact[i]);
      for j:=1 to i-1 do
        if a[j]>a[i] then dec(a[j]);
    end;
  end;
begin
  f:=-1;r:=0;for i:=0 to 8 do q[0,i]:=i;step[0]:=1;ans[id(q[0])]:=1;
  repeat
    inc(f);
    for m:=1 to 2 do begin
      inc(r);for i:=0 to 8 do q[r,i]:=q[f,move[m,i]];
      t:=id(q[r]);
      if ans[t]=0 then begin
        step[r]:=step[f]+1;ans[t]:=step[r];
      end
      else
        dec(r);
    end;
  until f=r;

  repeat
    for i:=0 to 8 do read(a[i]);
    writeln(ans[id(a)]-1);//There's nothing unsolvable
  until seekeof;
end.