Skip to content

1031: 大脸上课

题目

题目描述

由于dota水平太差被高手排斥,大脸同学最近迷上了打FIFA(虽然踢的依旧很臭)。一天晚上大脸通宵达旦和室友大战了三百回合,早上自然起晚了,可他又十分害怕迟到。

危难时刻,他拿出了自己的GPS,他发现以寝室为原点(坐标为$(0,0)$),上课教室的坐标为$(X,Y)$,每个时间单位他可以向东西南北某个方向走一步。如$(0,0)$可以到达$(0,1),(1,0),(0,-1),(-1,0)$。

他希望尽快走到教室,然而事情没有这么简单,因为一路上还有许多艰难险阻,比如大脸不会游泳,所以他不可能走到思春湖或者思源湖里(除非他觉得准时到达无望,一怒投湖)。具体来说,有N个障碍,第i个障碍的坐标是$(A_i, B_i)$。

于是大脸求助于你,请问大脸到达教室需要的最少时间是多少?

输入格式

第一行,三个整数$X,Y,N$。

第$2 \cdots N+1$行,第$i+1$行两个整数$(Ai, Bi)$。

输出格式

一行一个整数,表示大脸需要的最少时间。

样例输入

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

教室的坐标是$(1, 2)$. 障碍物是$(0, 2); (-1, 3); (3, 1); (1, 1); (4, 2); (-1, 1); (2, 2)$:

4 . . . . . . . . 3 . M . . . . . . 2 . . M C M . M . 1 . M . M . M . . 0 . . * . . . . . -1 . . . . . . . . -2-1 0 1 2 3 4 5

样例输出

11

*代表大脸的最佳线路。

4 ******* . . . . 3 * M . * . . . . 2 * . M C M . M . 1 * M . M . M . . 0 ***** . . . . . -1 . . . . . . . . -2-1 0 1 2 3 4 5

数据范围

30%的数据,$-20 \leq Ai, Bi, X, Y \leq 20$

50%的数据,$-100 \leq Ai, Bi, X, Y \leq 100$

100%的数据,$N\leq 10,000, -500 \leq Ai, Bi, X, Y \leq 500$

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!