시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 27 10 9 60.000%

문제

상근이는 매우 큰 저택에 갇혔다. 이 저택은 정사각형 모양의 방이 격자 모양으로 배치되어 있고, N행 M열 형태이다. 왼쪽으로부터 x(1 ≤ x ≤ M)번째, 아래쪽으로부터 y(1 ≤ y ≤ N)번째 방을 (x,y)라고 한다.

모든 인접한 방의 사이에는 문이 있다. 문은 열려있을 수도 있고, 닫혀있을 수도 있다. 다른 방으로 이동하는데 걸리는 시간(문을 통과하는데 걸리는 시간)은 1분이다. 상근이는 항상 열려있는 문으로만 이동할 수 있고, 개폐 상태를 바꿀 수는 없다.

어떤 방의 중앙에는 스위치가 있다. 이 스위치를 1분동안 누르고 있으면, 집에 있는 모든 문의 개폐 상태가 바뀌게 된다. 즉, 열려있던 문은 닫히게 되고, 닫혀있던 문은 열리게 된다.

저택의 크기와 스위치가 있는 방의 정보가 주어진다. 상근이는 지금 (1,1)방의 중앙에 있고, (M,N)방의 중앙으로 이동하려고 한다. 이 때, 이동할 수 있는 가장 빠른 시간을 구하는 프로그램을 작성하시오. 

가장 처음에 위아래로 인접한 방의 문만 열려있고, 나머지 문은 모두 닫혀있다.

입력

첫째 줄에 집의 크기 M, N과 스위치가 있는 방의 수 K가 주어진다. 둘째 줄부터 K개 줄에는 스위치가 있는 방의 위치 (xi, yi)가 주어진다. (2 ≤ M,N ≤ 100,000, 1 ≤ K ≤ 200,000)

출력

첫째 줄에 가장 빠른 시간을 출력한다. 만약, (M,N)에 도착할 수 없는 경우에는 -1을 출력한다.

예제 입력

3 2 1
1 2

예제 출력

4

힌트

(1,1)번에서 (3,2)으로 4분만에 이동할 수 있다.

1. (1,2)로 이동

2. (1,2)에 있는 스위치를 누른다.

3. (2,2)로 이동

4. (3,2)로 이동

집의 모습은 아래 그림에 나타나 있다. ×는 상근이의 위치, ○는 스위치이다. 

또, 아래의 경우에 답은 25이다.

출처

Olympiad > 일본정보올림피아드 > JOI 2013 3번