Problem 25216 --最远距离

25216: 最远距离

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 101  Solved: 36
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][92kb]

Description

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

Input

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

Output

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

Sample Input

3 3 0
001
001
110

Sample Output

1.414214

HINT

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

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

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

Source

[Submit][Status]