考虑到这道题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.