[SCOI2009]最长距离

Windy 有一块矩形土地，被划分为 $N\times M$ 个 $1\times 1$ 的小格子，其中一些格子含有障碍物。

若格子 $X$ 与格子 $Y$ 有公共边，且两个格子均不含障碍物，则可以从格子 $X$ 走到格子 $Y$。如果能从格子 $A$ 走到格子 $B$，则它们之间的距离定义为两个格子中心的欧几里得距离；否则，它们之间没有距离。

Windy 可以移走 $T$ 块障碍物。请在移除障碍物后，求所有能够互相到达的格子之间的最大距离。

保证移走 $T$ 块障碍物后，至少有一个格子不含障碍物。

输入格式

第一行包含三个整数 $N$、$M$、$T$。

接下来 $N$ 行，每行包含一个长度为 $M$ 的字符串。其中，字符 $0$ 表示空格子，字符 $1$ 表示该格子含有障碍物。

输出格式

输出一个浮点数，表示所有能够互相到达的格子之间的最大距离，保留 $6$ 位小数。

样例输入

样例 $1$：

3 3 0
001
001
110

样例 $2$：

4 3 0
001
001
011
000

样例 $3$：

3 3 1
001
001
001

样例输出

样例 $1$：

1.414214

样例 $2$：

3.605551

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

来源与许可

本题为 SCOI 2009 试题「最长距离」，题面与测试数据整理自 BZOJ。

样例 1

输入

3 3 0
001
001
110

输出

1.414214

样例 2

输入

4 3 0
001
001
011
000

输出

3.605551

样例 3

输入

3 3 1
001
001
001

输出

2.828427