/ Vijos / 题库 /

穿越泥地

穿越泥地

时间限制:1秒  内存限制:256M


【题目描述】

  清早6:00,FJ 就离开了他的屋子,开始了他的例行工作:为贝茜挤奶。前一天晚上,整个农场刚经受过一场瓢泼大雨的洗礼,于是不难想见,FJ 现在面对的是一大片泥泞的土地。FJ的屋子在平面坐标 \((0,0)\) 的位置,贝茜所在的牛棚则位于坐标 \((X,Y)\) 处。当然咯, FJ也看到了地上的所有 \(N\) 个泥塘,第 \(i\) 个泥塘的坐标为 \((A_i, B_i)\) 。每个泥塘都只占据了它所在的那个格子。

  Farmer John自然不愿意弄脏他新买的靴子,但他同时想尽快到达贝茜所在的位置。为了数那些讨厌的泥塘,他已经耽搁了一些时间了。如果Farmer John 只能平行于坐标轴移动,并且只在 \(x、y\) 均为整数的坐标处转弯,那么他从屋子门口出发,最少要走多少路才能到贝茜所在的牛棚呢?你可以认为从 FJ 的屋子到牛棚总是存在至少一条不经过任何泥塘的路径。

【输入格式】

  第 1 行: 3 个用空格隔开的整数:\(X,Y\) 和 \(N\)。
  第 \(2..N+1\) 行: 第 \(i+1\) 行为 2 个用空格隔开的整数:\(A_i\) 和 \(B_i\)

【输出格式】

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

【输入输出样例】

 Input

1 2 7
0 2
-1 3
3 1
1 1
4 2
-1 1
2 2

 Output

11

【输入输出样例解释】

  贝茜所在牛棚的坐标为(1, 2)。Farmer John能看到7个泥塘,它们的坐标分别为(0, 2)、(-1, 3)、(3, 1)、(1, 1)、(4, 2)、(-1, 1)以及(2, 2)。以下为农场的简图:(*为FJ的屋子,B为贝茜呆的牛棚)
说明
  约翰的最佳路线是:(0,0),(-1,0),(-2,0),(-2,1),(-2,2),(-2,3),(-2,4),(-1,4),(0,4), (0,3),(1,3),(1,2).

【数据限制】

  对于 \(100\%\) 的数据,\(1≤N≤10000\),\(-500≤X,Y≤500\),\(-500≤A_i,B_i≤500\)。

【来源】

  Mr.he

信息

ID
1916
难度
(无)
分类
搜索 | 图结构 | 最短路 点击显示
标签
递交数
0
已通过
0
通过率
?
被复制
9
上传者