관광

면접 대비

시간 제한1초메모리 제한128 MB

요약

북동 대각선이 추가된 격자에서 주어진 명소를 순서대로 방문할 때 이동한 도로 구간의 총합을 최소화합니다.

문제

제주시는 남북 $W$ 개, 동서 $H$ 개 도로가 격자를 이룬다. 북동 대각선 이동도 가능하다(단, 북쪽·동쪽 가장자리 교차로 제외). $N$ 개 관광지를 정해진 순서로 방문할 때 지나는 도로 수의 최솟값을 구한다.

첫 줄에 $W$ , $H$ , $N$ ( $2 \le W,H \le 10000$ , $1 \le N \le 1000$ ). 다음 $N$ 줄에 교차로 $(X_i, Y_i)$ .

순서대로 방문할 때 통과하는 도로 수의 최솟값을 출력한다.