1295: [SCOI2009]最长距离

 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.