AT_abc241_f [ABC241F] Skate

有一个 $H$ 行 $W$ 列的网格状滑冰场。第 $i$ 行第 $j$ 列的格子用 $(i,j)$ 表示。 滑冰场上有 $N$ 个障碍物，第 $i$ 个障碍物位于 $(X_i,Y_i)$。 高桥君每次移动时，可以选择上下左右任意一个方向，并一直滑行，直到撞到障碍物为止。 撞到障碍物时，会停在障碍物前一个格子。滑冰场四周是悬崖，不能进行不会撞到障碍物的移动。 高桥君一开始在 $(s_x,s_y)$，他希望通过若干次移动，最终停在 $(g_x,g_y)$。 到达 $(g_x,g_y)$ 至少需要多少次移动？如果无法到达，请输出无法到达的信息。

输入以如下格式从标准输入读入。 > $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 \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)$ - 所有输入均为整数 ### 样例解释 1  图中，$(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  必须停在 $(g_x,g_y)$。仅仅经过 $(g_x,g_y)$ 并不算到达。 ### 样例解释 3  如果选择向左移动，高桥君会经过 $(g_x,g_y)$ 后掉下悬崖。注意，滑冰场四周是悬崖，不能进行不会撞到障碍物的移动。 由 ChatGPT 4.1 翻译