TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P2065
  • 题目
  • P2065【SCOI2009 day2】最长距离
    限制 : 时间限制 : 20000 MS   空间限制 : 65536 KB
    问题描述

    windy有一块矩形土地,被分为 NM 块 11 的小格子。有的格子含有障碍物。
    如果从格子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
    【输入样例二】
    4 3 0
    001
    001
    011
    000
    【输入样例三】
    3 3 1
    001
    001
    001

    样例输出

    【输出样例一】
    1.414214
    【输出样例二】
    3.605551
    【输出样例三】
    2.828427

    提示

    20%的数据,满足 1 <= N,M <= 30 ; 0 <= T <= 0 。
    40%的数据,满足 1 <= N,M <= 30 ; 0 <= T <= 2 。
    100%的数据,满足 1 <= N,M <= 30 ; 0 <= T <= 30 。