Skate

题目描述

滑冰场用一个有 $H$ 行水平方向和 $W$ 列垂直方向的网格表示。记 $(i, j)$ 为从上数第 $i$ 行、从左数第 $j$ 列的格子。 滑冰场有 $N$ 个障碍物。第 $i$ 个障碍物放置在 $(X_i,Y_i)$。 在一次移动中，Takahashi 选择四个方向之一：上、下、左或右，并一直移动直到撞到一个障碍物。
当他撞到障碍物时，他停在障碍物前面的格子上。 由于滑冰场四周是悬崖，禁止开始一项移动如果该移动将导致他永远不会撞到障碍物。 Takahashi 最初位于 $(s_x,s_y)$。他想经过若干次移动停在 $(g_x,g_y)$。 求到达 $(g_x,g_y)$ 所需的最小移动次数。如果不可能，报告该事实。

输入格式

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$

输出格式

打印到达 $(g_x,g_y)$ 所需的最小移动次数。
如果不可能到达那里，打印 $-1$。

7 8 7
3 4
5 6
1 4
2 1
2 8
4 5
5 7
6 2
6 6

4

4 6 2
3 2
3 5
4 5
2 5

-1

1 10 1
1 5
1 1
1 7

-1

提示

$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. 图中，$(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)$。
他必须停在 $(g_x,g_y)$。
注意，仅仅经过 $(g_x,g_y)$ 并不算作到达目标。

如果他选择向左移动，Takahashi 在经过 $(g_x,g_y)$ 之后将会坠入悬崖。
注意禁止开始一项将导致他永远不会撞到障碍物的移动，因为滑冰场四周是悬崖。

标签: AtCoder|abc241F

来源

AtCoder|abc241F