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

考虑一个 N x N (1 <= N <= 100)的有1个个方格组成的正方形牧场。有些方格是奶牛们不能踏上的,它们被标记为了'x'。例如下图:

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

贝茜发现自己恰好在点A处,她想去B处的盐块舔盐。缓慢而且笨拙的动物,比如奶牛,十分讨厌转弯。尽管如此,当然在必要的时候她们还是会转弯的。对于一个给定的牧场,请你计算从A到B最少的转弯次数。开始的时候,贝茜可以使面对任意一个方向。贝茜知道她一定可以到达。

Input

第 1行: 一个整数 N 行

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

Output

行 1: 一个整数,最少的转弯次数。

Sample Input

3 .xA ... Bx.

Sample Output

2

HINT

Source

Silver

题解:(HansBug:太开心啦,这道题我又逗比啦哈哈哈 wnjxyk:汗= =)

其实虽然这道题也是个BFS水题,但是和一般的走迷宫问题相比,这道题有个坑点——对于一个点先遍历到的未必是最优的,其实就算是当前最优也由于在本题中由于涉及方向问题,所以对后续来说也未必最优,而如果简单的灌水法的话,则会由于遍历过了而导致真正的最优值无法被更新

如,数据中的第5个点:

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

但是(3,10)由于涉及来源于(2,10)的方向问题,所以很可能弄出个2作最优解,但事实上正解是1

说了这些就没了,继续AC

 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.       

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HansBug's Lab

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

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

30550
来自专栏HansBug's Lab

1601: [Usaco2008 Oct]灌水

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

30770
来自专栏HansBug's Lab

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
来自专栏HansBug's Lab

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

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

29170
来自专栏HansBug's Lab

1634: [Usaco2007 Jan]Protecting the Flowers 护花

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

33080
来自专栏HansBug's Lab

3314: [Usaco2013 Nov]Crowded Cows

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

27450
来自专栏HansBug's Lab

1602: [Usaco2008 Oct]牧场行走

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

29380
来自专栏HansBug's Lab

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

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

29870
来自专栏HansBug's Lab

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

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

27960

扫码关注云+社区

领取腾讯云代金券