1295: [SCOI2009]最长距离

1295: [SCOI2009]最长距离

Time Limit: 10 Sec  Memory Limit: 162 MB

Submit: 960  Solved: 498

[Submit][Status][Discuss]

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 。

Source

Day2

题解:又是一道搜索水题,直接灌水大法好。。。

 1 /**************************************************************
 2     Problem: 1295
 3     User: HansBug
 4     Language: Pascal
 5     Result: Accepted
 6     Time:3820 ms
 7     Memory:54448 kb
 8 ****************************************************************/
 9  
10 const
11         xx:array[1..4] of longint=(1,0,-1,0);
12         yy:array[1..4] of longint=(0,1,0,-1);
13 var
14         a:array[1..35,1..35,1..35,1..35,0..35] of boolean;
15         b:array[1..35,1..35,1..35,1..35] of boolean;
16         c:array[1..35,1..35] of boolean;
17         n,m,i,j,ii,jj,t:longint;
18         ch:char;
19         max:extended;
20 procedure dfs(x1,y1,x2,y2,zz:longint);
21         var
22                 i,j,x,y:longint;
23         begin
24                 b[x1,y1,x2,y2]:=true;
25                 a[x1,y1,x2,y2,zz]:=true;
26                 for i:=1 to 4 do begin
27                         x:=x2+xx[i]; y:=y2+yy[i];
28                         if (x>0) and (x<=n) and (y>0) and (y<=m) then
29                 begin
30                                     if (c[x,y]=false) and (zz+1<=t) and (a[x1,y1,x,y,zz+1]=false) then
31                         begin
32                                                 a[x1,y1,x,y,zz+1]:=true;
33                                                 dfs(x1,y1,x,y,zz+1);
34                                         end
35                     else
36                         if (c[x,y]=true) and (a[x1,y1,x,y,zz]=false) then
37                             begin
38                                                     a[x1,y1,x,y,zz]:=true;
39                                                     dfs(x1,y1,x,y,zz);
40                                             end;
41                             end;
42                 end;
43         end;
44 begin
45         readln(n,m,t);
46         fillchar(c,sizeof(c),true);
47         fillchar(a,sizeof(a),false);
48         fillchar(b,sizeof(b),false);
49         for i:=1 to n do
50         begin
51                     for j:=1 to m do
52                 begin
53                                 read(ch);
54                                 if ch='1' then c[i,j]:=false;
55                         end;
56                     readln;
57             end;
58         for i:=1 to n do
59                 for j:=1 to m do
60                         if c[i,j]=true then
61                            dfs(i,j,i,j,0)
62                         else
63                             if t>0 then dfs(i,j,i,j,1);
64         max:=0;
65         for i:=1 to n do
66                 for j:=1 to m do
67                         for ii:=1 to n do
68                                 for jj:=1 to m do
69                                         if (b[i,j,ii,jj]) and (sqrt(sqr(i-ii)+sqr(j-jj))>max) then max:=sqrt(sqr(i-ii)+sqr(j-jj));
70         writeln(max:0:6);
71 end.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏转载gongluck的CSDN博客

H.264格式分析

一.H.264基本流结构 H.264 的基本流(elementary stream,ES)的结构分为两层,包括视频编码层(VCL)和网络适配层(NAL)。视频编...

7405
来自专栏HansBug's Lab

1296: [SCOI2009]粉刷匠

1296: [SCOI2009]粉刷匠 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 916  Solved...

3615
来自专栏小樱的经验随笔

BZOJ 1800: [Ahoi2009]fly 飞行棋【思维题,n^4大暴力】

1800: [Ahoi2009]fly 飞行棋 Time Limit: 10 Sec  Memory Limit: 64 MB Submit: 1689  So...

3018
来自专栏智能算法

十张GIFs让你弄懂递归等概念

链接:http://codingpy.com/article/10-gifs-to-understand-some-programming-concepts/(...

3949
来自专栏ml

cf------(round)#1 C. Ancient Berland Circus(几何)

C. Ancient Berland Circus time limit per test 2 seconds memory limit per test ...

2523
来自专栏算法修养

HOJ 2133&POJ 2964 Tourist(动态规划)

Tourist Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 1503...

3648
来自专栏小樱的经验随笔

HDU 2080 夹角有多大II

夹角有多大II Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (J...

27610
来自专栏Flutter入门

Android OpenGL ES(二)-正交投影

平移矩阵和单位矩阵和类似。但是向量[x,y,z,1]前乘这个平移矩阵后的结构就是平移矩阵中定义的偏移量。

3691
来自专栏移动开发面面观

OpenGL ES——导入.stl格式的3D模型

2154
来自专栏数据结构与算法

BZOJ4517: [Sdoi2016]排列计数(组合数+错位排列)

Description 求有多少种长度为 n 的序列 A,满足以下条件: 1 ~ n 这 n 个数在序列中各出现了一次 若第 i 个数 的值为 i,则称 ...

2947

扫码关注云+社区

领取腾讯云代金券