J8 实践-3 最长距离

题目描述

$\text{windy}$ 有一块矩形土地，被分为 $N\times M$ 块 $1$ 的小格子。 有的格子含有障碍物。 如果从格子 $A$ 可以走到格子 $B$，那么两个格子的距离就为两个格子中心的欧几里德距离。 如果从格子 $A$ 不可以走到格子 $B$，就没有距离。 如果格子 $X$ 和格子 $Y$ 有公共边，并且 $X$ 和 $Y$ 均不含有障碍物，就可以从 $X$ 走到 $Y$。 如果 $\text{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

样例输出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$ 。