102415: [AtCoder]ABC241 F - Skate

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.

问题描述

有一个由$H$行和$W$列组成的滑冰场。记$(i, j)$表示从上数第$i$行、从左数第$j$列的方格。

滑冰场有$N$个障碍物。第$i$个障碍物放在$(X_i,Y_i)$处。

在一次移动中，高桥可以选择向上、向下、向左或向右四个方向之一，一直移动直到碰到障碍物。
当他碰到障碍物时，他会在障碍物前的方格停下。 由于滑冰场周围是悬崖，禁止开始一个他永远不会碰到障碍物的移动。

高桥最初在$(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)$后会掉下悬崖。
注意，由于滑冰场周围是悬崖，禁止开始一个他永远不会碰到障碍物的移动。