msquare.pas

来自「Magio牛的usaco源代码」· PAS 代码 · 共 83 行

{
ID:maigoak1
PROG:msquare
}

program msquare;
const
  fact:array[1..7]of integer=(1,2,6,24,120,720,5040);
  trans:array['A'..'C',1..8]of byte=((8,7,6,5,4,3,2,1),(4,1,2,3,6,7,8,5),(1,7,2,4,5,3,6,8));
var
  fin,fout:text;
  q:array[1..40320]of record
      state:string[8];
      op:'A'..'C';
      pre:longint;
    end;
  v:array[1..40320]of boolean;
  d,t:string[8];
  front,rear:longint;
  x,i:byte;
  c:char;
function hash(s:string[8]):longint;
  var
    i,j:byte;
  begin
    hash:=1;
    for i:=1 to 7 do begin
      inc(hash,fact[8-i]*(ord(s[i])-49));
      for j:=i+1 to 7 do
        if s[j]>s[i] then dec(s[j]);
    end;
  end;
procedure out;
  var
    ans:string;
  begin
    ans:='';
    while rear>1 do begin
      ans:=q[rear].op+ans;
      rear:=q[rear].pre;
    end;
    assign(fout,'msquare.out');
    rewrite(fout);
    writeln(fout,length(ans));
    writeln(fout,ans);
    close(fout);
    halt;
  end;
begin
  assign(fin,'msquare.in');
  reset(fin);
  d:='';
  for i:=1 to 8 do begin
    read(fin,x);
    d:=d+chr(x+48);
  end;
  close(fin);

  fillchar(v,sizeof(v),0);
  q[1].state:='12345678';
  v[1]:=true;
  front:=0;rear:=1;
  if q[1].state=d then out;
  repeat
    inc(front);
    for c:='A' to 'C' do begin
      t:='';
      for i:=1 to 8 do
        t:=t+q[front].state[trans[c,i]];
      if not v[hash(t)] then begin
        inc(rear);
        with q[rear] do begin
          state:=t;
          op:=c;
          pre:=front;
        end;
        if t=d then out;
        v[hash(t)]:=true;
      end;
    end;
  until false;
end.