考虑到这道题n，m都很小，我们考虑先穷举起点i
下面我们要做的是找出移走k个障碍后，点i所能到的最大距离
我们可以把这个问题转化为判定性问题
对于一对点i,j,如果他们之间存在一条路径，障碍数（包括起点终点）小于k，那么这两个点的点间距就是可行间距
也就是说，我们对于每个起点，我们只要做一遍最短路径，然后穷举找到最大可行间距即可(因为图的边数较少）
1 const dx:array[1..4] of integer=(0,0,-1,1); 2 dy:array[1..4] of integer=(1,-1,0,0); 3 type node=record 4 point,len,next:longint; 5 end; 6 7 var a,num:array[0..40,0..40] of longint; 8 p,d:array[0..1010] of longint; 9 edge:array[0..50010] of node; 10 q:array[0..100010] of longint; 11 v:array[0..1010] of boolean; 12 t,h,i,j,k,n,m,x,y:longint; 13 ans:double; 14 s:string; 15 16 function max(a,b:double):double; 17 begin 18 if a>b then exit(a) else exit(b); 19 end; 20 21 function calc(x1,y1,x2,y2:longint):double; 22 begin 23 exit(sqrt(sqr(x1-x2)+sqr(y1-y2))); 24 end; 25 26 procedure add(x,y,c:longint); 27 begin 28 inc(h); 29 edge[h].point:=y; 30 edge[h].len:=c; 31 edge[h].next:=p[x]; 32 p[x]:=h; 33 end; 34 35 procedure spfa(st:longint); 36 var f,r,x,y,i:longint; 37 begin 38 f:=1; 39 r:=1; 40 q[1]:=st; 41 while f<=r do 42 begin 43 x:=q[f]; 44 v[x]:=false; 45 i:=p[x]; 46 while i<>-1 do 47 begin 48 y:=edge[i].point; 49 if d[y]>d[x]+edge[i].len then 50 begin 51 d[y]:=d[x]+edge[i].len; 52 if not v[y] then 53 begin 54 inc(r); 55 q[r]:=y; 56 v[y]:=true; 57 end; 58 end; 59 i:=edge[i].next; 60 end; 61 inc(f); 62 end; 63 end; 64 65 begin 66 fillchar(p,sizeof(p),255); 67 readln(n,m,t); 68 for i:=1 to n do 69 begin 70 readln(s); 71 for j:=1 to m do 72 begin 73 a[i,j]:=ord(s[j])-48; 74 inc(k); 75 num[i,j]:=k; 76 end; 77 end; 78 for i:=1 to n do 79 for j:=1 to m do 80 for k:=1 to 4 do 81 begin 82 x:=i+dx[k]; 83 y:=j+dy[k]; 84 if num[x,y]>0 then add(num[i,j],num[x,y],a[x,y]) 85 end; 86 87 for i:=1 to n do 88 for j:=1 to m do 89 begin 90 fillchar(v,sizeof(v),false); 91 v[num[i,j]]:=true; 92 for k:=1 to n*m do 93 d[k]:=10000; 94 d[num[i,j]]:=a[i,j]; 95 spfa(num[i,j]); 96 for k:=1 to n*m do 97 if d[k]<=t then 98 ans:=max(ans,calc(i,j,(k-1) div m+1,(k-1) mod m+1)); 99 end; 100 writeln(ans:0:6); 101 end.