「BZOJ1295」[SCOI2009] 最长距离

2014年1月16日2,4473

Description

windy有一块矩形土地,被分为 N*M 块 1*1 的小格子。 有的格子含有障碍物。 如果从格子A可以走到格子B,那么两个格子的距离就为两个格子中心的欧几里德距离。 如果从格子A不可以走到格子B,就没有距离。 如果格子X和格子Y有公共边,并且X和Y均不含有障碍物,就可以从X走到Y。 如果windy可以移走T块障碍物,求所有格子间的最大距离。 保证移走T块障碍物以后,至少有一个格子不含有障碍物。

Input

输入文件maxlength.in第一行包含三个整数,N M T。 接下来有N行,每行一个长度为M的字符串,’0’表示空格子,’1’表示该格子含有障碍物。

Output

输出文件maxlength.out包含一个浮点数,保留6位小数。

Sample Input

「输入样例一」
3 3 0
001
001
110 

「输入样例二」
4 3 0
001
001
011
000

「输入样例三」
3 3 1
001
001
001

Sample Output

「输出样例一」
1.414214 

「输出样例二」
3.605551

「输出样例三」
2.828427

HINT

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

代码

再打了一遍。。

 

说点什么

提醒
avatar
Refun
Refun

黄学长您的第一个代码是不是错了啊QvQ我和您的拍大数据能拍出错来
30 30 1
011111100010001010000010001001
111001101011000110000110110011
110001001101100001101011101011
000010011000101110001010001000
100100110000000100101100001011
011010000111101000110010111111
001011101101010010000001100100
010011000111110011110100000010
001000001111111100011000000100
100110100001010000001001111100
011011010011011010101101011001
010011011101001100110000100110
000111011000101100111100011011
110100100010010110110100000001
010111001010001111101010100111
110001010000101101111110001101
001111111001110101010111001101
011101011110111000010110011011
100110001010111001100010111101
001011010011110011101000100001
010011001001010010000011101110
000110011000101011111100101100
001110110111101111011010101011
010010100100000110100010000111
100110010000010101100000011000
110100010000011010101000110110
111111000011110011001111000011
000111111000110001111101111011
001011011010111111000110110001
100101110010111111110011010100
答案好像应该是26.683328(逃

某果蝇

第36行为什么有一个nx<xx跳过啊?不能往上走吗?

某果蝇

重打的那个