実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
H 行 W 列のグリッド型のスケート場があります。上から i 行目、左から j 行目のマスを (i,j) で表します。
スケート場には N 個の障害物があり、i 個目の障害物は (X_i,Y_i) に置かれています。
高橋君は 1 回の移動において、上下左右いずれかの方向を選んで、障害物に当たるまで進み続けます。
障害物に当たるとその 1 つ手前のマスで停止します。
なお、スケート場の周りは崖になっており、障害物に当たらないような移動は禁止とします。
高橋君ははじめ (s_x,s_y) にいて、何回か移動することで (g_x,g_y) で停止したいと考えています。
(g_x,g_y) へ辿り着くには最小で何回の移動が必要ですか?辿り着けないときはその旨を伝えてください。
制約
- 1\leq H \leq 10^9
- 1\leq W \leq 10^9
- 1\leq N \leq 10^5
- 1\leq s_x,g_x\leq H
- 1\leq s_y,g_y\leq W
- 1\leq X_i \leq H
- 1\leq Y_i \leq W
- (s_x,s_y)\neq (g_x,g_y)
- (s_x,s_y)\neq (X_i,Y_i)
- (g_x,g_y)\neq (X_i,Y_i)
- i\neq j ならば、(X_i,Y_i)\neq (X_j,Y_j)
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
H W N s_x s_y g_x g_y X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
出力
(g_x,g_y) へ辿り着くには最小で何回の移動が必要か出力せよ。
ただし、辿り着けないならば -1
と出力せよ。
入力例 1
7 8 7 3 4 5 6 1 4 2 1 2 8 4 5 5 7 6 2 6 6
出力例 1
4
図は、(s_x,s_y) を S
で、(g_x,g_y) を G
で表しています。
(3,4)\rightarrow(2,4) \rightarrow(2,2) \rightarrow(5,2) \rightarrow(5,6) と移動すると、4 回の移動で (g_x,g_y) に辿り着くことができます。
入力例 2
4 6 2 3 2 3 5 4 5 2 5
出力例 2
-1
(g_x,g_y) で停止する必要があります。
通過しただけでは (g_x,g_y) へ辿り着いたとみなされないことに注意してください。
入力例 3
1 10 1 1 5 1 1 1 7
出力例 3
-1
左を選んで進むと、高橋君は (g_x,g_y) を通過したのちに崖に落ちてしまいます。
スケート場の周りは崖になっており、障害物に当たらないような移動は禁止されていることに注意してください。
Score : 500 points
Problem Statement
There is a skating rink represented by a grid with H horizontal rows and W vertical columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.
The skating rink has N obstacles. The i-th obstacle is placed at (X_i,Y_i).
In a single move, Takahashi chooses one of the four directions, up, down, left, or right, and keeps moving until he hits an obstacle.
When he hits an obstacle, he stops at the square right before the obstacle.
Since the skating rink is surrounded by cliffs, it is prohibited to start a move in which he will never hit an obstacle.
Takahashi is initially at (s_x,s_y). He wants to make some number of moves to stop at (g_x,g_y).
Find the minimum number of moves required to end up at (g_x, g_y). If it is not possible, report the fact.
Constraints
- 1\leq H \leq 10^9
- 1\leq W \leq 10^9
- 1\leq N \leq 10^5
- 1\leq s_x,g_x\leq H
- 1\leq s_y,g_y\leq W
- 1\leq X_i \leq H
- 1\leq Y_i \leq W
- (s_x,s_y)\neq (g_x,g_y)
- (s_x,s_y)\neq (X_i,Y_i)
- (g_x,g_y)\neq (X_i,Y_i)
- If i\neq j, then (X_i,Y_i)\neq (X_j,Y_j).
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
H W N s_x s_y g_x g_y X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
Output
Print the minimum number of moves required to end up at (g_x,g_y).
If it is impossible to end up there, print -1
.
Sample Input 1
7 8 7 3 4 5 6 1 4 2 1 2 8 4 5 5 7 6 2 6 6
Sample Output 1
4
In the figure, (s_x,s_y) is denoted by S
and (g_x,g_y) is denoted by G
.
By moving as (3,4)\rightarrow(2,4) \rightarrow(2,2) \rightarrow(5,2) \rightarrow(5,6), he can end up at (g_x,g_y) with 4 moves.
Sample Input 2
4 6 2 3 2 3 5 4 5 2 5
Sample Output 2
-1
He must stop at (g_x,g_y).
Note that just passing through (g_x,g_y) is not considered to be ending up at the goal.
Sample Input 3
1 10 1 1 5 1 1 1 7
Sample Output 3
-1
If he chooses to move to the left, Takahashi will fall down the cliff after passing through (g_x,g_y).
Note that it is prohibited to start a move in which he will never hit an obstacle, as the skating rink is surrounded by cliffs.