문제 번호 6133 --초거대도시 (超都観光)

6133: 초거대도시 (超都観光)

시간 제한: 1 Sec  메모리 제한: 128 MB
제출: 1  해결 문제 수: 1
[제출][채점상황][게시판][:]

문제 설명

번역 : 경남과학고 29기 도회린
오번역이나 문제에 관한 질문은 게시판을 이용해주세요.

 JOI군은 IOI나라에 있는 어떤 초거대도시의 여행을 계획하게 되었다.

 도시에는 남북으로 똑바로 뻗어있는 W개의 도로와, 동서로 똑바로 뻗어있는 H개의 도로가 바둑판처럼 이루고 있다.

 남북 방향의 W개의 도로에는 서쪽으로부터 순서대로 1, 2, ..., W의 번호를 붙이고, 동서 방향의 도로에는 남쪽으로부터 순서대로 1, 2, …, H의 번호가 붙어있다. 서쪽에서 i번째 남북 방향 도로와, 남쪽에서 j번째 동서 방향 도로의 교차점을 (i, j)로 나타낸다.

 뿐만 아니라, 각 교차점에는 아래 그림과 같이 북동에서 남서 방향으로 뻗어있는 대각선 도로도 존재한다. 즉 하나의 교차점에서 동, , , , 북동, 남서의 여섯 방향으로 이동이 가능하다. (, 가장 끝 쪽에 위치하여 도로가 존재하지 않는 교차점의 경우는 예외이다.)

 입력은 1+N개의 줄로 이루어진다.

 첫 번째 줄에는 세 개의 정수 W, H, N이 공백으로 구분되어 주어진다. WH는 각각 2 이상 10,000 이하의 자연수이며, N1 이상 1,000 이하의 자연수이다.

 이어지는 N개의 줄에는 JOI군이 정한 관광지의 좌표 (X(i), Y(i))가 방문할 순서대로 주어진다.

출력

 모든 관광지를 방문해야 할 때 반드시 통과해야 하는 도로의 개수(여러 번 지나간 길은 여러 번으로 셈)를 정수로 출력한다.

입력예시

예시 1)
4 3 3
1 1
3 3
4 1

예시 2)
4 3 5
1 3
4 3
2 2
2 2
1 3

출력예시

출력 예시 1)
5

출력 예시 2)
7

도움말



 예시 1)에서는 (1, 1) – (2, 2) – (3, 3) – (3, 2) – (4, 2) – (4, 1) 순서로 이동하면 길을 다섯 번 지나고 모든 관광지를 방문할 수 있다.


 예시 2)에서는 (1, 3) – (2, 3) – (3, 3) – (4, 3) – (3, 2) – (2, 2) – (1, 2) – (1, 3)의 순서로 이동하여 길을 일곱 번 지나고 모든 관광지를 방문할 수 있다.


 출발 지점이 (1, 1)이 아니라 (X(1), Y(1))임에 유의하자.


출처

[제출][채점상황]