F - Skate Editorial /

Time Limit: 2 sec / Memory Limit: 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.