4071: 穿越泥地(mud)

Memory Limit:128 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:169 Solved:91

Description

【问题描述】

    清早600FJ就离开了他的屋子,开始了他的例行工作:为贝茜挤奶。前一天晚上,整个农场刚经受过一场瓢泼大雨的洗礼,于是不难想象,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)。每个泥塘都只占据了它所在的那个格子。
    FJ自然不愿意弄脏他新买的靴子,但他同时想尽快到达贝茜所在的位置。为了数那些讨厌的泥塘,他已经耽搁了一些时间了。如果FJ只能平行于坐标轴移动,并且只在xy均为整数的坐标处转弯,那么他从屋子门口出发,最少要走多少路才能到贝茜所在的牛棚呢?你可以认为从FJ的屋子到牛棚总是存在至少一条不经过任何泥塘的路径。
【输入格式】
1: 3个用空格隔开的整数:XY  N
2..N+1: i+1行为2个用空格隔开的整数:A_i  B_i
【输出格式】
输出1个整数,即FJ在不踏进泥塘的情况下,到达贝茜所在牛棚所需要走过的最小距离。
【输入样例】
1 2 7
0 2
-1 3
3 1
1 1
4 2
-1 1
2 2
【输出样例】
11
样例说明:
    贝茜所在牛棚的坐标为(1, 2)FJ能看到7个泥塘,它们的坐标分别为(0, 2)(-1, 3)(3, 1)(1, 1)(4, 2)(-1, 1)以及(2, 2)FJ的最佳路线是:(0, 0)(-1, 0)(-2, 0)(-2, 1)(-2, 2)(-2, 3)(-2, 4)(-1, 4)(0, 4)(0, 3)(1, 3)(1, 2)


加入题单

上一题 下一题 算法标签: