P6558: 最远距离
传统题
1.000s
时间限制
128MB
内存限制
3 提交
3 解决
【题目描述】
whitecloth 有一块矩形土地，被分为N*M 块1*1 的小格子。有的格子含有障碍物。如果从格子A 可以走到格子B，那么两个格子的距离就为两个格子中心的欧几里德距离。如果从格子A 不可以走到格子B，就没有距离。如果格子X 和格子Y 有公共边，并且X 和Y 均不含有障碍物，就可以从X 走到Y。如果whitecloth 可以移走T 块障碍物，求所有格子间的最大距离。保证移走T 块障碍物以后，至少有一个格子不含有障碍物。
【输入】
第一行包含三个整数，N M T。
接下来有N 行，每行一个长度为M 的字符串，'0'表示空格子，'1'表示该格子含有障碍物。
【输出】
一个数表示答案，保留6 位小数
【样例输入】复制
3 3 0
001
001
110
【提示】
对于20%的数据，满足1 <= N,M <= 30 ，0 <= T <= 0
对于40%的数据，满足1 <= N,M <= 30 ，0 <= T <= 2
对于100%的数据，满足1 <= N,M <= 30 ，0 <= T <= 30