CF2215G Maze

有一个 $ (n+2) \times (n+2) $ 的网格，横纵坐标的范围均为 $0$ 到 $n+1$（包含端点）。这个网格的最外层的所有格子都是障碍格。 此外，网格中还有 $m$ 个障碍格。第 $i$ 个障碍格的位置为 $(x_i, y_i)$。保证所有的障碍格（包括外圈边界障碍格）是 4-连通的。也就是说，从任意一个障碍格出发，通过上、下、左、右方向移动，总能到达任意其它障碍格。 小 L 正在迷宫中行走。他不允许进入任何障碍格。如果小 L 当前在 $(x, y)$，他可以进行以下移动： - 正交移动：向相邻的 $(x+1,y)$、$(x-1,y)$、$(x,y+1)$ 或 $(x,y-1)$ 移动，花费 $2$。 - 对角移动：向相邻的 $(x+1,y+1)$、$(x+1,y-1)$、$(x-1,y+1)$ 或 $(x-1,y-1)$ 移动，花费 $3$。 有 $q$ 个询问。对于每个询问，给定一个起点和一个终点。你需要求出小 L 从起点走到终点的最小总花费。如果无法到达终点，输出 $-1$。

第一行包含三个整数 $n$、$m$ 和 $q$，其中 $1 \le n \le 10^5$，$1 \le m, q \le 3 \times 10^5$。 接下来 $m$ 行，每行两个整数 $x_i$ 和 $y_i$，表示第 $i$ 个障碍格子的坐标。保证所有障碍格坐标互不相同，并且所有障碍格（包括外圈边界）是 4-连通的。 接下来 $q$ 行，每行四个整数 $s_x$、$s_y$、$t_x$ 和 $t_y$，表示一次询问的起点 $(s_x, s_y)$ 和终点 $(t_x, t_y)$。保证 $(s_x, s_y)$ 和 $(t_x, t_y)$ 都不是障碍格。

对于每个询问，输出一个整数，表示从起点到终点的最小花费。如果不能到达则输出 $-1$。

对于第二个询问，可以这样移动：$(1,1) \to (1,2) \to (2,3) \to (3,4) \to (4,3) \to (4,2) \to (3,1)$。总代价为 $2+3+3+3+2+3=16$。 由 ChatGPT 5 翻译