camelot.pas

Magio牛的usaco源代码

{
ID:maigoak1
PROG:camelot
}

program camelot;
const
  maxc=26;
  maxr=40;
  maxgrid=maxc*maxr;
  dc:array[1..8]of shortint=(2,1,-1,-2,-2,-1,1,2);
  dr:array[1..8]of shortint=(1,2,2,1,-1,-2,-2,-1);
  near=5;
type
  coord=record
    c,r:byte;
  end;
var
  fin,fout:text;
  knight:array[0..maxgrid-1]of coord;{knight[0] is the king}
  len:array[1..maxc,1..maxr,1..maxc,1..maxr]of integer;{APSP}
  cols,rows:byte;
  knights,ans:integer;
  ch:char;
function min(a,b:integer):integer;
  begin
    if a<b then min:=a else min:=b;
  end;
function max(a,b:integer):integer;
  begin
    if a>b then max:=a else max:=b;
  end;
function kingdist(x,y:integer):integer;
  begin
    kingdist:=max(abs(x-knight[0].c),abs(y-knight[0].r));
  end;
procedure readdata;
  begin
    assign(fin,'camelot.in');
    reset(fin);
    readln(fin,rows,cols);
    knights:=-1;
    repeat
      repeat
        read(fin,ch);
      until (ch>='A') and (ch<='Z') or eof(fin);
      if eof(fin) then break;
      inc(knights);
      knight[knights].c:=ord(ch)-64;
      read(fin,knight[knights].r);
    until false;
    close(fin);
  end;
procedure APSP;
  var
    q:array[1..maxgrid]of record
        c,r:integer;
      end;
    i,j,k,x,y,front,rear:integer;
  begin
    for i:=1 to cols do
      for j:=1 to rows do begin
        for x:=1 to cols do
          for y:=1 to rows do
            len[i,j,x,y]:=maxint;
        len[i,j,i,j]:=0;
        front:=0;rear:=1;
        with q[1] do begin c:=i;r:=j;end;
        repeat
          inc(front);
          for k:=1 to 8 do begin
            x:=q[front].c+dc[k];y:=q[front].r+dr[k];
            if (x>0) and (x<=cols) and (y>0) and (y<=rows) and (len[i,j,q[front].c,q[front].r]+1<len[i,j,x,y]) then begin
              inc(rear);
              with q[rear] do begin c:=x;r:=y;end;
              len[i,j,x,y]:=len[i,j,q[front].c,q[front].r]+1;
            end;
          end;
        until front=rear;
      end;
  end;
procedure oneknight;
  var
    i,j:byte;
  begin
    ans:=maxint;
    for i:=max(1,knight[0].c-near) to min(cols,knight[0].c+near) do
      for j:=max(1,knight[0].r-near) to min(rows,knight[0].r+near) do begin
        if len[knight[1].c,knight[1].r,i,j]<maxint then
          ans:=min(ans,len[knight[1].c,knight[1].r,i,j]+kingdist(i,j));
        if (len[knight[1].c,knight[1].r,knight[0].c,knight[0].r]<maxint) and (len[knight[0].c,knight[0].r,i,j]<maxint) then
          ans:=min(ans,len[knight[1].c,knight[1].r,knight[0].c,knight[0].r]+len[knight[0].c,knight[0].r,i,j]);
      end;
  end;
procedure multiknight;
  var
    avec,aver,i,l1,l2,l3:integer;
    c1,r1,c2,r2:byte;
      {c1,r1: Where all people meet}
      {c2,r2: Where a knight meets the king}
    flag:boolean;
  begin
    ans:=maxint;
    avec:=0;aver:=0;
    for i:=1 to knights do avec:=avec+knight[i].c;avec:=avec div knights;
    for i:=1 to knights do aver:=aver+knight[i].r;aver:=aver div knights;

    for c1:=max(1,avec-near) to min(cols,avec+near) do
      for r1:=max(1,aver-near) to min(rows,aver+near) do begin
        l1:=0;
        flag:=true;
        for i:=1 to knights do
          if len[c1,r1,knight[i].c,knight[i].r]<maxint then
            l1:=l1+len[c1,r1,knight[i].c,knight[i].r]
          else begin
            flag:=false;
            break;
          end;
        if flag then
          for c2:=max(1,knight[0].c-near) to min(cols,knight[0].c+near) do
            for r2:=max(1,knight[0].r-near) to min(rows,knight[0].r+near) do begin
              l2:=l1+kingdist(c2,r2);
              for i:=1 to knights do begin
                if len[c2,r2,knight[i].c,knight[i].r]<maxint then begin
                  l3:=l2-len[knight[i].c,knight[i].r,c1,r1]+len[knight[i].c,knight[i].r,c2,r2]+len[c2,r2,c1,r1];
                  if l3<ans then ans:=l3;
                end;
              end;
            end;
      end;
  end;
begin
  readdata;

  if knights=0 then
    ans:=0
  else if knights=1 then begin
    APSP;
    oneknight;
  end
  else begin
    APSP;
    multiknight;
  end;

  assign(fout,'camelot.out');
  rewrite(fout);
  writeln(fout,ans);
  close(fout);
end.