问题 25216. -- 最远距离

25216: 最远距离

时间限制: 1 Sec  内存限制: 128 MB
献花: 1  解决: 1
[献花][花圈]

题目描述

      whitecloth 有一块矩形土地,被分为N*M 块1*1 的小格子。有的格子含有障碍物。如果从格子A 可以走到格子B,那么两个格子的距离就为两个格子中心的欧几里德距离。如果从格子A 不可以走到格子B,就没有距离。如果格子X 和格子Y 有公共边,并且X 和Y 均不含有障碍物,就可以从X 走到Y。如果whitecloth 可以移走T 块障碍物,求所有格子间的最大距离。保证移走T 块障碍物以后,至少有一个格子不含有障碍物。

输入

第一行包含三个整数,N M T。
接下来有N 行,每行一个长度为M 的字符串,'0'表示空格子,'1'表示该格子含有障碍物。

输出

一个数表示答案,保留6 位小数

样例输入

3 3 0
001
001
110

样例输出

1.414214

提示

对于20%的数据,满足1 <= N,M <= 30 ,0 <= T <= 0

对于40%的数据,满足1 <= N,M <= 30 ,0 <= T <= 2

对于100%的数据,满足1 <= N,M <= 30 ,0 <= T <= 30

来源

[献花][花圈]