You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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$ 位小数。

3 3 0
001
001
110

1.414214

4 3 0
001
001
011
000

3.605551

3 3 1
001
001
001

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$。