← 返回题目列表

AtCoder · abc241_f

I. 滑冰

中文机器翻译题面 查看原题

分数: 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).
请注意,禁止开始永远不会碰到障碍物的动作,因为溜冰场周围都是悬崖。