2738 : 꽃게
- 제한시간
- 2000 ms
- 메모리제한
- 256 MB
- 해결횟수
- 5 회
- 시도횟수
- 64 회
문제
서쪽의 노을을 바라보고 있는 꽃게 연준이가 광활한 모래밭의 한복판(1, 1)에서 자신의 집(M, N)까지 가려고 한다. 알다시피, 꽃게는 옆으로만 움직일 수 있기 때문에 처음에는 연준이가 남/북으로만 움직일 수 있다.
한편, 모래밭에는 K개의 돌림판이 있어서 돌림판 위에서는 연준이가 90도 회전할 수 있다. (정확히 90도씩만 회전할 수 있다.) 이 점을 이용해서 연준이는 돌림판을 잘 사용해서 날이 어둑어둑해지기 전에 빨리 집으로 가려고 한다.
연준이가 1만큼 움직이거나 90도 회전할 때 1의 시간이 걸린다고 할 때, 연준이가 집으로 갈 때 걸리는 최소 시간을 구하여라. 단, 동/서쪽으로 1만큼 움직이면 x좌표가 1/-1씩 증가하며, 남/북쪽으로 1만큼 움직이면 y좌표가 -1/1씩 증가한다.
입력형식
첫 번째 줄에는 연준이의 집의 좌표를 나타내는 자연수 M, N 과 돌림판의 수 K가 주어진다.
(1 ≤ M, N ≤ 100,000, 1 ≤ K ≤ 200,000)
두 번째 줄부터 K개의 줄에는 돌림판의 좌표 Xi, Yi (1 ≤ Xi ≤ M, 1 ≤ Yi ≤ N)가 주어진다.
전체 데이터의 20%는 M, N ≤ 1,000을 만족한다.
전체 데이터의 40%는 K ≤ 2,000을 만족한다.
전체 데이터의 60%는 위 조건 중 하나 이상을 만족한다.
출력형식
연준이가 자신의 집까지 갈 수 있는 최소 시간을 출력한다. 만약 연준이가 집까지 갈 수 없다면 -1을 출력한다.
입력 예복사하기 3 2 1 1 2 |
출력 예복사하기 4 |
입력 예복사하기 3 2 1 2 1 |
출력 예복사하기 -1 |
입력 예복사하기 8 9 15 3 1 3 2 3 7 3 8 1 1 4 5 4 3 5 6 5 8 6 3 6 2 7 5 8 9 8 6 8 5 |
출력 예복사하기 26 |
Hint!
