문제 번호 6223 --현대적인 저택(現代的な屋敷)

6223: 현대적인 저택(現代的な屋敷)

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

문제 설명

문제번역 : 경남과학고 29기 도회린

당신은 어떤 저택에서 길을 헤매고 있다. 이 저택은 사각형 모양의 방이 동서남북으로 격자를 이루고 있으며, 동서방향으로 M, 남북방향으로 N행이 늘어서있다.

서쪽에서 x번째, 남쪽에서 y번째에 있는 방의 좌표를 (x, y)라고 하자. 동서남북으로 나란히 붙어 있는 방은 벽의 가운데에 있는 문을 통해 연결되어있다. 각각의 문은 잠겨있어서 지나갈 수 없거나, 열려 있어서 지나갈 수 있는 두 가지 상태 중 하나에 있다. 문이 열려있을 때, 옆방의 한 가운데로 이동하는데 1분이 걸린다. 또한, 몇 개의 방 한 가운데에는 스위치가 설치되어있다. 스위치를 1분간 누르면, 저택 안의 잠긴 문은 열리고, 열린 문은 잠긴다.

지금, 동서로 이웃한 방을 연결하는 문은 모두 잠겨있고, 남북으로 이웃한 방을 연결하는 문은 모두 열려있다. 당신은 지금 방 (1, 1)의 한 가운데에 있고, (M, N)의 한 가운데까지 최단 시간으로 이동하고 싶다.

예를 들어, M=3, N=2이고, (1, 2) 위치의 방에 스위치가 설치되어있다고 하자. 아래와 같은 과정을 통해 이동 시간은 최소 4분이 걸린다는 것을 알 수 있다.

저택의 크기인 M, N값과, 스위치가 설치되어있는 방의 개수 K, 그리고 스위치가 설치되어있는 방의 좌표 (X1, Y1), (X2, Y2), ..., (Xk, Yk) 값이 주어졌을 때, (1, 1) 위치의 방에서 (M, N) 위치의 방으로 이동하는 최단 시간을 분 단위로 구하여라.

입력

첫 번째 줄에는 정수 M, N, K가 공백으로 구분되어 주어진다. 이 때, M, N2100,000사이의 정수, K1200,000사이의 정수이다.

이어지는 K개의 줄에는 스위치가 설치되어있는 방의 좌표가 한 줄에 하나씩 주어진다.

 

출력

문제 조건에 해당하는 최단 시간을 분 단위의 정수로 출력한다. 만약 (M, N) 위치의 방까지 갈 수 없다면 1을 출력한다.

입력예시

「입력 예시 1」
3 2 1
1 2

「입력 예시 2」
3 2 1
2 1

「입력 예시 3」
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

출력예시

「출력 예시 1」
4

「출력 예시 2」
-1

「출력 예시 3」
25

도움말

입출력 예시 3번을 그림으로 나타내자면 아래와 같다.


출처

[제출][채점상황]