ac1114.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1114;
const
  maxsize=10;
  maxp=30000;
  dx:array[1..4]of shortint=(0,0,1,-1);
  dy:array[1..4]of shortint=(1,-1,0,0);
var
  map:array[0..maxsize+1,0..maxsize+1]of char;
  dist:array[1..maxsize,1..maxsize,1..maxsize,1..maxsize]of shortint;
  farthest:array[1..maxsize,1..maxsize]of byte;
  x,y:array[0..maxp]of byte;
  t:array[0..maxp]of longint;
  catch,max:array[0..maxp]of word;
  n,m,i,j,p:integer;
procedure bfs(sx,sy:byte);
  var
    f,r,i,u,v:byte;
  begin
    f:=0;r:=1;x[1]:=sx;y[1]:=sy;dist[sx,sy,sx,sy]:=0;
    repeat
      inc(f);
      for i:=1 to 4 do begin
        u:=x[f]+dx[i];v:=y[f]+dy[i];
        if (map[u,v]='.') and (dist[sx,sy,u,v]<0) then begin
          inc(r);x[r]:=u;y[r]:=v;dist[sx,sy,u,v]:=dist[sx,sy,x[f],y[f]]+1;
        end;
      end;
    until f=r;
    farthest[sx,sy]:=dist[sx,sy,x[r],y[r]];
  end;
procedure qsort(s,e:word);
  var
    p,i,j,tx,ty,tt:longint;
  begin
    if s>=e then exit;
    p:=s+random(e-s+1);
    tx:=x[p];ty:=y[p];tt:=t[p];x[p]:=x[s];y[p]:=y[s];t[p]:=t[s];
    i:=s;j:=e;
    repeat
      while (i<j) and (t[j]>=tt) do dec(j);
      if i=j then break;x[i]:=x[j];y[i]:=y[j];t[i]:=t[j];inc(i);
      while (i<j) and (t[i]<=tt) do inc(i);
      if i=j then break;x[j]:=x[i];y[j]:=y[i];t[j]:=t[i];dec(j);
    until i=j;
    x[i]:=tx;y[i]:=ty;t[i]:=tt;
    qsort(s,i-1);
    qsort(i+1,e);
  end;
begin
  repeat
    readln(n,m);
    for i:=1 to n do begin
      for j:=1 to m do begin
        read(map[i,j]);
        if map[i,j]='L' then begin
          x[0]:=i;y[0]:=j;map[i,j]:='.';
        end;
      end;
      readln;
    end;

    fillchar(dist,sizeof(dist),255);
    bfs(x[0],y[0]);
    for i:=1 to n do
      for j:=1 to n do
        if dist[x[0],y[0],i,j]>0 then bfs(i,j);

    read(j);p:=0;
    for i:=1 to j do begin
      inc(p);read(x[p],y[p],t[p]);if dist[x[0],y[0],x[p],y[p]]<0 then dec(p);
    end;
    qsort(1,p);

    for i:=1 to p do begin
      catch[i]:=0;
      if t[i]>=dist[x[0],y[0],x[i],y[i]] then begin
        j:=i-1;
        while (j>0) and (t[i]-t[j]<farthest[x[i],y[i]]) do begin
          if dist[x[j],y[j],x[i],y[i]]<=t[i]-t[j] then
            if catch[j]>catch[i] then catch[i]:=catch[j];
          dec(j);
        end;
        if j>0 then if max[j]>catch[i] then catch[i]:=max[j];
        inc(catch[i]);
      end;
      if catch[i]>max[i-1] then max[i]:=catch[i] else max[i]:=max[i-1];
    end;
    writeln(max[p]);
  until seekeof;
end.