Informatica Online Judge

  Vaccine [0724 / 02D4]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 12   Total Tried : 14


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[]

Background

(주) 경곽전자의 유능한 프로그래머 진형과 범수는 서로 라이벌 관계이다. 이번에 경곽전자에서 야심차게 준비하여 발표한 GSHS_HDD는 n*n 정사각형 그리드형 하드디스크이다. 범수는 자신의 탁월한 유비트 학습 알고리즘을 이용하여 체스의 나이트 모양으로 움직이는 신형 백신 Ukisa_Bum을 개발하였으며, 이름에서부터 알 수 있듯이 진형은 자신의 주특기인 “구라”를 이용하여 자신의 백신을 새로운 형태의 백신인 양 속여서 Ukisa_Bum과 사실은 똑같은 Liar_Jin을 개발하였다.

GSHS_HDD에 이전 버전에서 S.T.A.(Speedy Teleporting Access) 기능이 새로 추가되어, 백신이 (x1,y1)에 도달하였을 때, 시간지연 없이 (x2,y2)로 Teleport를 할 수 있다.
(물론 거꾸로도 갈 수 있다.)

이 S.T.A. 기능과 두 가지 신형 백신을 테스트하기 위하여 m개의 바이러스를 순차적으로 발생시킨다. CPU는 두 백신의 위치를 알고 있어서 두 백신 중 한 백신에게 바이러스를 치료하라고 명령을 내린다.

(주) 경곽전자의 사장은 모든 바이러스를 치료하는 데 걸리는 최소 시간을 알고자 한다.
(단, Liar_Jin과 Ukisa_Bum은 처음에 (1,1)과 (n,n)에 있다. 또한, 체스의 나이트 모양으로 1번 움직일 때 1μs가 걸리며, 위대한 범수신의 능력으로 백신은 하드디스크 밖을 돌아다닐 수 있으며, 바이러스를 치료하는 데 걸리는 시간은 없다!!!!)

Input

첫째 줄에 두 정수 n, m이 입력된다. ( 1 <= n, m <= 1000 )
둘째 줄에는 네 정수 x1, y1, x2, y2가 입력된다. ( 1 <= x1, y1, x2, y2 <= n )
셋째 줄부터 m+2 째 줄까지 사건이 발생한 위치가 두 개의 정수로 주어진다.
(각 좌표는 1이상 n이하의 정수)

Output

바이러스를 모두 치료하는데 걸리는 최소시간을 구한다.

IO Example

입력
4 3
2 2 2 3
4 3
3 2
2 4

출력
4

*출제 : 29th 권태호

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]