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

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

Time Limit: 5 Sec  Memory Limit: 64 MB

Submit: 383  Solved: 196

[Submit][Status][Discuss]

Description

. . B x . . x x A . . . . x . . x . . . . . x . .

Input

2..N + 1: 行 i+1 有 N 个字符 ('.', 'x', 'A', 'B')，表示每个点的状态。

3 .xA ... Bx.

2

Source

Silver

33 .......xA.....x.......x.......... ...x...........x.........x....... ........x.xx.....x.x............. .....x.....x.........x........... .....x................x.x........ ......x..x....x.........xx....... ...................x......x...... ...x.....x....................x.. ....x..........................x. x................................ ................................. .....x...x..x.................... .............................x... ...................x.........x... ...............x...x....x...x.... ..........xx.......x..x.......... ................................x ..............................xx. ..x...............x.x............ .x....x...............x....x....x ..x......xx.......x.x.......x.... ................x...xx.....x.x..x .x.............x........x...x.x.. .............................x.x. .........................x......x .....x.......x............xx...xx ........x....x.....xx.x.....xx.x. ...........x...x........x.x...xxB .x.x.x.............x...........x. x.............x................x. .........x.x.....x.....x.....x... ........x..............xx.....x.. ..............xx......x.x.....x..

（2，10）位置上最优值显然是1，而且无论怎么遍历都是1

``` 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
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
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;
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);
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.       ```

0 条评论

相关文章

1688: [Usaco2005 Open]Disease Manangement 疾病管理

1688: [Usaco2005 Open]Disease Manangement 疾病管理 Time Limit: 5 Sec  Memory Limit: ...

30550

1601: [Usaco2008 Oct]灌水

1601: [Usaco2008 Oct]灌水 Time Limit: 5 Sec  Memory Limit: 162 MB Submit: 1342  S...

30770

3433: [Usaco2014 Jan]Recording the Moolympics

3433: [Usaco2014 Jan]Recording the Moolympics Time Limit: 10 Sec  Memory Limit:...

28040

BZOJ1046: [HAOI2007]上升序列(LIS)

对于一个给定的S={a1,a2,a3,…,an},若有P={ax1,ax2,ax3,…,axm},满足(x1 < x2 < … < xm)且（ ax1 < ...

10030

1734: [Usaco2005 feb]Aggressive cows 愤怒的牛

1734: [Usaco2005 feb]Aggressive cows 愤怒的牛 Time Limit: 5 Sec  Memory Limit: 64 MB...

29170

1634: [Usaco2007 Jan]Protecting the Flowers 护花

1634: [Usaco2007 Jan]Protecting the Flowers 护花 Time Limit: 5 Sec  Memory Limit:...

33080

3314: [Usaco2013 Nov]Crowded Cows

3314: [Usaco2013 Nov]Crowded Cows Time Limit: 1 Sec  Memory Limit: 128 MB Submit...

27450

1602: [Usaco2008 Oct]牧场行走

1602: [Usaco2008 Oct]牧场行走 Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 1211  ...

29380

1724: [Usaco2006 Nov]Fence Repair 切割木板

1724: [Usaco2006 Nov]Fence Repair 切割木板 Time Limit: 5 Sec  Memory Limit: 64 MB Su...

29870

1741: [Usaco2005 nov]Asteroids 穿越小行星群

1741: [Usaco2005 nov]Asteroids 穿越小行星群 Time Limit: 5 Sec  Memory Limit: 64 MB Sub...

27960