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

输入 #1

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

输出 #1

4

输入输出样例 #2

输入 #2

4 6 2
3 2
3 5
4 5
2 5

输出 #2

-1

输入输出样例 #3

输入 #3

1 10 1
1 5
1 1
1 7

输出 #3

-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 翻译