시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 505 | 242 | 226 | 49.670% |
상근이는 재환이와 함께 제주도에 여행을 가기로 했다.
제주시는 남북방향 도로 W개와 동서방향 도로 H개로 이루어져 있으며, 바둑판 모양을 이루고 있다.
남북방향 도로는 서쪽에서부터 차례대로 1, 2, ..., W가 매겨져 있고, 동서방향 도로는 남쪽에서부터 차례대로 1, 2, ..., H가 매겨져 있다. i번째 남북 도로와 j번째 동서 도로로 이루어진 교차로를 (i, j)로 나타낸다.
제주시에는 북동방향 도로도 존재한다. 가장 북쪽의 도로와 동쪽 도로에 있는 교차로를 제외한 모든 교차로에는 북동방향 도로가 존재한다. 즉, 교차로 (i,j)에서 (i-1,j-1)이나 (i+1,j+1)이 존재하는 경우에는 그 교차로로 한 번에 이동할 수 있다.
재환이는 자신이 방문하고 싶은 관광지 N개를 미리 정해왔다. i번째로 방문할 관광지는 (Xi, Yi)에 있다. 상근이는 여행에 걸리는 시간을 최소로 하기 위해서 통과해야 하는 길의 개수를 적게 하려고 한다. 관광지를 재환이가 정한 순서대로 방문하면서 지나야 하는 길의 최소 개수를 구하는 프로그램을 작성하시오.
여행은 (X1, Y1)에서 시작한다. 또한, 여행 도중에 도시 밖으로는 이동할 수 없다. 상근이와 재환이는 같은 길을 두 번 이상 통과할 수 있으며, 한 도로를 여러 번 방문하는 경우에는 방문하는 만큼 중복해서 계산한다.
첫째 줄에 W, H, N이 주어진다. (2 ≤ W, H ≤ 10000, 1 ≤ N ≤ 1000)
둘째 줄부터 N개 줄에는 관광지의 위치 Xi, Yi가 주어진다.
관광지를 재환이가 정한 순서대로 방문하면서 통과하는 길의 최소 개수를 출력한다.
4 3 3 1 1 3 3 4 1
5
(1,1), (2,2), (3,3), (3,2), (4,2), (4,1) 순서로 방문하면 된다.