1627: [Usaco2007 Dec]穿越泥地

1627: [Usaco2007 Dec]穿越泥地

Time Limit: 5 Sec  Memory Limit: 64 MB

Submit: 504  Solved: 325

[Submit][Status]

Description

清早6:00,Farmer John就离开了他的屋子,开始了他的例行工作:为贝茜挤奶。前一天晚上,整个农场刚经受过一场瓢泼大雨的洗礼,于是不难想见,FJ 现在面对的是一大片泥泞的土地。FJ的屋子在平面坐标(0, 0)的位置,贝茜所在的牛棚则位于坐标(X,Y) (-500 <= X <= 500; -500 <= Y <= 500)处。当然咯, FJ也看到了地上的所有N(1 <= N <= 10,000)个泥塘,第i个泥塘的坐标为 (A_i, B_i) (-500 <= A_i <= 500;-500 <= B_i <= 500)。每个泥塘都只占据了它所在的那个格子。 Farmer John自然不愿意弄脏他新买的靴子,但他同时想尽快到达贝茜所在的位置。为了数那些讨厌的泥塘,他已经耽搁了一些时间了。如果Farmer John 只能平行于坐标轴移动,并且只在x、y均为整数的坐标处转弯,那么他从屋子门口出发,最少要走多少路才能到贝茜所在的牛棚呢?你可以认为从FJ的屋子到牛棚总是存在至少一条不经过任何泥塘的路径。

Input

* 第1行: 3个用空格隔开的整数:X,Y 和 N

* 第2..N+1行: 第i+1行为2个用空格隔开的整数:A_i 和 B_i

Output

* 第1行: 输出1个整数,即FJ在不踏进泥塘的情况下,到达贝茜所在牛棚所需要 走过的最小距离

Sample Input

1 2 7 0 2 -1 3 3 1 1 1 4 2 -1 1 2 2 输入说明: 贝茜所在牛棚的坐标为(1, 2)。Farmer John能看到7个泥塘,它们的坐标分 别为(0, 2)、(-1, 3)、(3, 1)、(1, 1)、(4, 2)、(-1, 1)以及(2, 2)。 以下为农场的简图:(*为FJ的屋子,B为贝茜呆的牛棚) 4 . . . . . . . . 3 . M . . . . . . Y 2 . . M B M . M . 1 . M . M . M . . 0 . . * . . . . . -1 . . . . . . . . -2-1 0 1 2 3 4 5 X

Sample Output

11

HINT

    约翰的最佳路线是:(0,0),(一1,0),(一2,0),(一2,1),(一2,2),(一2,3),(一2,4),(一1,4),(0,4),  (0,3),  (1,3),  (1,2).

Source

Silver

 题解:炒鸡可爱的一道BFS,也没啥,主要就是将已经来过的点全部剪枝掉,注意假如设边界的话,最好将(-501..501)×(-501..501)设为合法的边界——题目中可没规定这个地图是有限的,可是既然泥潭范围为(-500..500)×(-500..500),那就扩展一个就是了(所以个人觉得题目中保证有可行路径这一条完全多余了——对于无限地图怎么可能没有通路?)然后没啥了。。。(才剪枝到这个程度的BFS都能100ms我也是醉了*^_^*)

 1 var
 2    i,j,k,l,m,n,f,r,x,y:longint;
 3    a:array[-510..510,-510..510] of longint;
 4    b:array[0..1500000,1..2] of longint;
 5 begin
 6      readln(x,y,n);
 7      fillchar(a,sizeof(a),0);
 8      for i:=1 to n do
 9          begin
10               readln(j,k);
11               a[j,k]:=-1;
12          end;
13      for i:=-502 to 502 do
14          begin
15               a[i,-502]:=-1;
16               a[i,502]:=-1;
17               a[-502,i]:=-1;
18               a[502,i]:=-1;
19          end;
20      f:=1;r:=2;b[1,1]:=0;b[1,2]:=0;
21      a[0,0]:=1;
22      while f<r do
23            begin
24                 if a[b[f,1]+1,b[f,2]]=0 then
25                    begin
26                         b[r,1]:=b[f,1]+1;
27                         b[r,2]:=b[f,2];
28                         a[b[r,1],b[r,2]]:=a[b[f,1],b[f,2]]+1;
29                         if (b[r,1]=x) and (b[r,2]=y) then
30                            begin
31                                 writeln(a[b[r,1],b[r,2]]-1);
32                                 halt;
33                            end;
34                         inc(r);
35                    end;
36                 if a[b[f,1]-1,b[f,2]]=0 then
37                    begin
38                         b[r,1]:=b[f,1]-1;
39                         b[r,2]:=b[f,2];
40                         a[b[r,1],b[r,2]]:=a[b[f,1],b[f,2]]+1;
41                         if (b[r,1]=x) and (b[r,2]=y) then
42                            begin
43                                 writeln(a[b[r,1],b[r,2]]-1);
44                                 halt;
45                            end;
46                         inc(r);
47                    end;
48                 if a[b[f,1],b[f,2]+1]=0 then
49                    begin
50                         b[r,1]:=b[f,1];
51                         b[r,2]:=b[f,2]+1;
52                         a[b[r,1],b[r,2]]:=a[b[f,1],b[f,2]]+1;
53                         if (b[r,1]=x) and (b[r,2]=y) then
54                            begin
55                                 writeln(a[b[r,1],b[r,2]]-1);
56                                 halt;
57                            end;
58                         inc(r);
59                    end;
60                 if a[b[f,1],b[f,2]-1]=0 then
61                    begin
62                         b[r,1]:=b[f,1];
63                         b[r,2]:=b[f,2]-1;
64                         a[b[r,1],b[r,2]]:=a[b[f,1],b[f,2]]+1;
65                         if (b[r,1]=x) and (b[r,2]=y) then
66                            begin
67                                 writeln(a[b[r,1],b[r,2]]-1);
68                                 halt;
69                            end;
70                         inc(r);
71                    end;
72                 inc(f);
73            end;
74 end.
75                 

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏chenjx85的技术专栏

leetcode-682-Baseball Game

13840
来自专栏小樱的经验随笔

图论----同构图(详解)

图论当中的术语,假设G=(V,E)和G1=(V1,E1)是两个图,如果存在一个双射m:V→V1,使得对所有的x,y∈V均有xy∈E等价于m(x)m(y)∈E1,...

60180
来自专栏小樱的经验随笔

2017广东工业大学程序设计竞赛决赛 题解&源码(A,数学解方程,B,贪心博弈,C,递归,D,水,E,贪心,面试题,F,贪心,枚举,LCA,G,dp,记忆化搜索,H,思维题)

心得: 这比赛真的是不要不要的,pending了一下午,也不知道对错,直接做过去就是了,也没有管太多! Problem A: 两只老虎 Description ...

33660
来自专栏机器学习从入门到成神

一道面试题到卡特兰数及其应用

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

14620
来自专栏PPV课数据科学社区

用Python分析苹果公司股价数据

作者:酱油哥,清华程序猿、IT非主流 专栏地址: https://zhuanlan.zhihu.com/c_147297848 要点抢先看 1.csv数据的读...

40550
来自专栏WOLFRAM

用 Wolfram 语言来做2017年高考数学试题之天津理科卷

19440
来自专栏数说工作室

统计师的Python日记【第3天:Numpy你好】

本文是【统计师的Python日记】第3天的日记 回顾一下,第1天学习了Python的基本页面、操作,以及几种主要的容器类型;第2天学习了python的函数、循环...

497120
来自专栏Python中文社区

用Python分析苹果公司股价数据

专栏地址:https://zhuanlan.zhihu.com/c_147297848

12020
来自专栏WOLFRAM

九宫格数独游戏

27080
来自专栏PPV课数据科学社区

【学习】《R实战》读书笔记(第五章)

读书会是一种在于拓展视野、宏观思维、知识交流、提升生活的活动。PPV课R语言读书会以“学习、分享、进步”为宗旨,通过成员协作完成R语言专业书籍的精读和分享,达到...

51390

扫码关注云+社区

领取腾讯云代金券