分数: 500 点
问题陈述
有一个用网格表示的溜冰场, 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)
- If 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),他最终可能会在 (g_x,g_y) 与 4 移动。
示例输入 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).
请注意,禁止开始永远不会碰到障碍物的动作,因为溜冰场周围都是悬崖。