1644: [Usaco2007 Oct]Obstacle Course 障碍训练课

 1 /**************************************************************
 2     Problem: 1644
 3     User: HansBug
 4     Language: Pascal
 5     Result: Accepted
 6     Time:32 ms
 7     Memory:1728 kb
 8 ****************************************************************/
 9  
10 const dd:array[1..4,1..2] of longint=((1,0),(-1,0),(0,1),(0,-1));
11 var
12    i,j,k,l,m,n,x0,y0,x1,y1,f,r,x,y:longint;
13    b:array[0..205,0..205] of longint;
14    a:array[0..205,0..205] of longint;
15    d:array[0..100000,0..2] of longint;
16    ch:char;
17 function min(x,y:longint):longint;
18          begin
19               if x<y then min:=x else min:=y;
20          end;
21 function max(x,y:longint):longint;
22          begin
23               if x>y then max:=x else max:=y;
24          end;
25  
26 begin
27      readln(n);
28      fillchar(b,sizeof(b),0);
29      fillchar(a,sizeof(a),0);
30      for i:=0 to n+1 do
31          begin
32               b[0,i]:=1;
33               b[n+1,i]:=1;
34               b[i,0]:=1;
35               b[i,n+1]:=1;
36          end;
37      for i:=1 to n do
38          begin
39               for j:=1 to n do
40                   begin
41                        read(ch);
42                        case upcase(ch) of
43                             ‘.‘:b[i,j]:=0;
44                             ‘A‘:begin
45                                      x0:=i;y0:=j;
46                                      b[i,j]:=1;
47                             end;
48                             ‘B‘:begin
49                                      x1:=i;y1:=j;
50                                      b[i,j]:=0;
51                             end;
52                             ‘X‘:b[i,j]:=1;
53                        end;
54                   end;
55               readln;
56          end;
57      f:=1;r:=2;d[1,1]:=x0;d[1,2]:=y0;
58      a[x0,y0]:=1;a[x0,y0]:=1;a[x0,y0]:=1;a[x0,y0]:=1;
59      while f<r do
60            begin
61                 for i:=1 to 4 do
62                     begin
63                          x:=d[f,1];y:=d[f,2];
64                          while true do
65                                begin
66                                     x:=x+dd[i,1];
67                                     y:=y+dd[i,2];
68                                     if b[x,y]=1 then break;
69                                     l:=a[d[f,1],d[f,2]]+1;
70                                     if (l>=a[x,y]) and (a[x,y]>0) then continue;
71                                     a[x,y]:=l;
72                                     if (x=x1) and (y=y1) then
73                                        begin
74                                             writeln(a[x,y]-2);
75                                             readln;
76                                             halt;
77                                        end;
78                                     d[r,1]:=x;d[r,2]:=y;
79                                     inc(r);
80                                end;
81  
82                     end;
83                 inc(f);
84            end;
85 end.