200ms

{$inline on}

const

  qsize=1 shl 18;

  di:array [0..4,0..1] of integer=((0,0),(1,0),(-1,0),(0,-1),(0,1));

type

  bty=array [1..3,0..1] of word;

  bta=dword;

var

  map:array [1..16,1..16] of char;

  dt:array [0..qsize] of bta;

  dis:array [0..16777215] of integer;

  i,j,w,h,n,basval:integer;

  a,b,fr,ti:bty;

  ans:integer;

  f,r:longint;

procedure encode(var x:dword);

begin

  x:=0;

  x:=(b[1][0]-1)or((b[1][1]-1) shl 4);

  x:=x or ((b[2][0]-1)or((b[2][1]-1) shl 4)) shl 8;

  x:=x or ((b[3][0]-1)or((b[3][1]-1) shl 4)) shl 16;

end;

procedure decode(x:dword);

begin

  a[1][0]:=x and $f+1;

  a[1][1]:=(x and $f0) shr 4+1;

  a[2][0]:=(x and $f00) shr 8+1;

  a[2][1]:=(x and $f000) shr 12+1;

  a[3][0]:=(x and $f0000) shr 16+1;

  a[3][1]:=(x and $f00000) shr 20+1;

end;

function valid(i:integer):boolean;inline;

begin

  valid:=(b[i][0]>0)and(b[i][0]<=h)

  and(b[i][1]>0)and(b[i][1]<=w)

  and(map[b[i][0]][b[i][1]]<>'#');

end;

function same(i,j:integer):boolean;inline;

begin

  same:=(b[i][0]=b[j][0])and(b[i][1]=b[j][1]);

end;

function exchanged(i,j:integer):boolean;inline;

begin

  exchanged:=(a[i][0]=b[j][0])and(a[i][1]=b[j][1])

  and(a[j][0]=b[i][0])and(a[j][1]=b[i][1]);

end;

procedure push(x:bta;d:integer);

begin

  dt[r]:=x;

  r:=(r+1)and(qsize-1);

  dis[x]:=d;

end;

function bfs:integer;

var

  i1,i2,i3,e1,e2,e3:integer;

  x,y:bta;

begin

  f:=1;r:=1;

  b:=fr;encode(x);

  push(x,basval+1);

  b:=ti;encode(x);

  push(x,-basval-1);

  e1:=4;e2:=4;e3:=4;

  if n<3 then e3:=0;

  if n<2 then e2:=0;

  while (f<>r) do

  begin

    x:=dt[f];f:=(f+1)and(qsize-1);

    decode(x);

    if dis[x]>0 then begin

      for i1:=0 to e1 do

      begin

        b[1][0]:=a[1][0]+di[i1][0];

        b[1][1]:=a[1][1]+di[i1][1];

        if not valid(1) then continue;

        for i2:=0 to e2 do

        begin

          b[2][0]:=a[2][0]+di[i2][0];

          b[2][1]:=a[2][1]+di[i2][1];

          if (n>1) and (not valid(2) or same(1,2) or exchanged(1,2)) then continue;

          for i3:=0 to e3 do

          begin

            b[3][0]:=a[3][0]+di[i3][0];

            b[3][1]:=a[3][1]+di[i3][1];

            if (n>2) and (not valid(3) or same(1,3) or exchanged(1,3) or same(2,3) or exchanged(2,3)) then continue;

            encode(y);

            if dis[y]>basval then continue;

            if dis[y]<-basval then begin

              bfs:=(dis[x]-dis[y]-1-2*basval);

              inc(basval,1000);

              exit;

            end

            else

             push(y,dis[x]+1);

          end;

        end;

      end;

    end

    else begin

      for i1:=0 to e1 do

      begin

        b[1][0]:=a[1][0]+di[i1][0];

        b[1][1]:=a[1][1]+di[i1][1];

        if not valid(1) then continue;

        for i2:=0 to e2 do

        begin

          b[2][0]:=a[2][0]+di[i2][0];

          b[2][1]:=a[2][1]+di[i2][1];

          if (n>1) and (not valid(2) or same(1,2) or exchanged(1,2)) then continue;

          for i3:=0 to e3 do

          begin

            b[3][0]:=a[3][0]+di[i3][0];

            b[3][1]:=a[3][1]+di[i3][1];

            if (n>2) and (not valid(3) or same(1,3) or exchanged(1,3) or same(2,3) or exchanged(2,3)) then continue;

            encode(y);

            if dis[y]<-basval then continue;

            if dis[y]>basval then begin

              bfs:=(dis[y]-dis[x]-1-2*basval);

              inc(basval,1000);

              exit;

            end

            else

              push(y,dis[x]-1);

          end;

        end;

      end;

    end;

  end;

  exit(-1);

end;

begin

  basval:=0;

  readln(w,h,n);

  while (w<>0)and(h<>0)and(n<>0) do

  begin

    for i:=1 to h do

    begin

      for j:=1 to w do

      begin

        read(map[i][j]);

        case map[i][j] of

          'a':begin fr[1][0]:=i;fr[1][1]:=j; end;

          'b':begin fr[2][0]:=i;fr[2][1]:=j; end;

          'c':begin fr[3][0]:=i;fr[3][1]:=j; end;

          'A':begin ti[1][0]:=i;ti[1][1]:=j; end;

          'B':begin ti[2][0]:=i;ti[2][1]:=j; end;

          'C':begin ti[3][0]:=i;ti[3][1]:=j; end;

        end;

      end;

      readln;

    end;

    for i:=n+1 to 3 do begin fr[i][0]:=1;fr[i][1]:=1;ti[i][0]:=1;ti[i][1]:=1; end;

    ans:=bfs;

    writeln(ans);

    readln(w,h,n);

  end;

end.

• 8个月之后居然还记得 楼主威武 (5258) zhendeluzi 2010-12-19 15:53:30
  • 好长…… (0) dzzhanshen 2010-12-19 20:07:35