[SCOI2009] 最长距离
题目描述
windy 有一块矩形土地,被分为 $N\times M$ 块 $1\times 1$ 的小格子。 有的格子含有障碍物。 如果从格子 A 可以走到格子 B,那么两个格子的距离就为两个格子中心的欧几里德距离。 如果从格子 A 不可以走到格子 B,就没有距离。如果格子 X 和格子 Y 有公共边,并且 X 和 Y 均不含有障碍物,就可以从 X 走到 Y。 如果 windy 可以移走 $T$ 块障碍物,求所有格子间的最大距离。保证移走 $T$ 块障碍物以后,至少有一个格子不含有障碍物。
输入输出格式
输入格式
第一行包含三个整数,$N,M,T$。 接下来有 $N$ 行,每行一个长度为 $M$ 的字符串,`0` 表示空格子,`1` 表示该格子含有障碍物。
输出格式
包含一个浮点数,保留 $6$ 位小数。
输入输出样例
输入样例 #1
3 3 0
001
001
110
输出样例 #1
1.414214
输入样例 #2
4 3 0
001
001
011
000
输出样例 #2
3.605551
输入样例 #3
3 3 1
001
001
001
Sample Output
输出样例 #3
2.828427
说明
- $20\%$ 的数据,满足 $1 \le N,M \le 30 $,$ 0 \le T \le 0 $。
- $40\%$ 的数据,满足 $1 \le N,M \le 30 $,$ 0 \le T \le 2 $。
- $100\%$ 的数据,满足 $1 \le N,M \le 30 $,$ 0 \le T \le 30$。