JOI 2013/2014 예선 3- 여행 > 문제은행 : 정보올림피아드&알고리즘




2733 : 여행

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
15 회   
시도횟수
26 회   

문제

은비는 관광 명소로 유명한 소울시에서 여행을 계획하고 있다.

 

소울시는 남북 방향으로 뻗은 W개의 도로와 동서 방향으로 뻗은 H개의 도로에 의해 격자 모양으로 이루어져 있다. 남북 방향의 W개의 도로는 서쪽에서부터 차례대로 1, 2, ..., W의 번호가 매겨져 있고, 동서 방향의 H개의 도로는 남쪽에서부터 차례대로 1, 2, ..., H의 번호가 매겨져 있다. 서쪽에서 a번째 남북 방향의 도로와 남쪽에서 b번째 동서 방향의 도로의 교차로는 (a, b)로 표시된다.

 

또, 아래 그림과 같이 각 교차로의 북동쪽-남서쪽 방향으로 도로가 뻗어져 있다. 따라서 교차로 (a, b)에서 1개의 도로를 통해 (a-1, b), (a+1, b), (a, b-1), (a, b+1), (a-1, b-1), (a+1, b+1)로 갈 수 있고, 이 여섯 가지 경우 모두 1의 시간이 걸린다.

 

 

 

은비는 N개의 관광 명소를 어떤 순서로 방문할지 모두 계획했다. i번째로 방문할 관광 명소는 교차로 (Xi, Yi)에 있다. 은비가 N개의 관광 명소를 방문하는 데 걸리는 최소 시간을 구하는 프로그램을 작성하여라. 단, 은비는 (X1, Y1)에서 여행을 시작하며, 같은 길을 두 번 이상 통과할 수 있다.


입력형식

첫 번째 줄에는 도시의 크기 W, H와 방문하는 관광 명소의 수 N이 주어진다. (2 ≤ W, H ≤ 10,000, 1 ≤ N ≤ 1,000) 두 번째 줄부터 N개의 줄에는 각 관광 명소의 좌표 Xi, Yi가 주어진다. (1 ≤ Xi ≤ W, 1 ≤ Yi ≤ H)

출력형식

은비가 N개의 관광 명소를 방문하는 데 걸리는 최소 시간을 출력한다.

입력 예

4 3 3
1 1
3 3
4 1

출력 예

5

입력 예

4 3 5
1 3
4 3
2 2
2 2
1 3

출력 예

7

Hint!

첫 번째 예제의 경우, 은비가 (1, 1), (2, 2), (3, 3), (3, 2), (4, 2), (4, 1)의 순서로 교차로를 지나가면 된다.



경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP