考虑到这道题n,m都很小,我们考虑先穷举起点i

下面我们要做的是找出移走k个障碍后,点i所能到的最大距离

我们可以把这个问题转化为判定性问题

对于一对点i,j,如果他们之间存在一条路径,障碍数(包括起点终点)小于k,那么这两个点的点间距就是可行间距

也就是说,我们对于每个起点,我们只要做一遍最短路径,然后穷举找到最大可行间距即可(因为图的边数较少)

 const dx:array[..] of integer=(,,-,);
      dy:array[..] of integer=(,-,,);
type node=record
       point,len,next:longint;
     end; var a,num:array[..,..] of longint;
    p,d:array[..] of longint;
    edge:array[..] of node;
    q:array[..] of longint;
    v:array[..] of boolean;
    t,h,i,j,k,n,m,x,y:longint;
    ans:double;
    s:string; function max(a,b:double):double;
  begin
    if a>b then exit(a) else exit(b);
  end; function calc(x1,y1,x2,y2:longint):double;
  begin
    exit(sqrt(sqr(x1-x2)+sqr(y1-y2)));
  end; procedure add(x,y,c:longint);
  begin
    inc(h);
    edge[h].point:=y;
    edge[h].len:=c;
    edge[h].next:=p[x];
    p[x]:=h;
  end; procedure spfa(st:longint);
  var f,r,x,y,i:longint;
  begin
    f:=;
    r:=;
    q[]:=st;
    while f<=r do
    begin
      x:=q[f];
      v[x]:=false;
      i:=p[x];
      while i<>- do
      begin
        y:=edge[i].point;
        if d[y]>d[x]+edge[i].len then
        begin
          d[y]:=d[x]+edge[i].len;
          if not v[y] then
          begin
            inc(r);
            q[r]:=y;
            v[y]:=true;
          end;
        end;
        i:=edge[i].next;
      end;
      inc(f);
    end;
  end; begin
  fillchar(p,sizeof(p),);
  readln(n,m,t);
  for i:= to n do
  begin
    readln(s);
    for j:= to m do
    begin
      a[i,j]:=ord(s[j])-;
      inc(k);
      num[i,j]:=k;
    end;
  end;
  for i:= to n do
    for j:= to m do
      for k:= to do
      begin
        x:=i+dx[k];
        y:=j+dy[k];
        if num[x,y]> then add(num[i,j],num[x,y],a[x,y])
      end;   for i:= to n do
    for j:= to m do
    begin
      fillchar(v,sizeof(v),false);
      v[num[i,j]]:=true;
      for k:= to n*m do
        d[k]:=;
      d[num[i,j]]:=a[i,j];
      spfa(num[i,j]);
      for k:= to n*m do
        if d[k]<=t then
          ans:=max(ans,calc(i,j,(k-) div m+,(k-) mod m+));
    end;
  writeln(ans::);
end.
05-08 08:24