Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 960 Solved: 498
windy有一块矩形土地,被分为 N*M 块 1*1 的小格子。 有的格子含有障碍物。 如果从格子A可以走到格子B,那么两个格子的距离就为两个格子中心的欧几里德距离。 如果从格子A不可以走到格子B,就没有距离。 如果格子X和格子Y有公共边,并且X和Y均不含有障碍物,就可以从X走到Y。 如果windy可以移走T块障碍物,求所有格子间的最大距离。 保证移走T块障碍物以后,至少有一个格子不含有障碍物。
输入文件maxlength.in第一行包含三个整数,N M T。 接下来有N行,每行一个长度为M的字符串,'0'表示空格子,'1'表示该格子含有障碍物。
输出文件maxlength.out包含一个浮点数,保留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 。
题解:又是一道搜索水题,直接灌水大法好。。。
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.