← 返回题目列表

Codeforces · 2215/G

G. 迷宫

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

有一个 $$$(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 \cdot 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$$$。

示例

输入
复制

4 4 5
2 1
2 2
3 2
3 3
1 1 1 2
1 1 3 1
4 1 1 4
4 4 1 1
2 3 3 1

输出
复制

2
16
11
10
11

注意

对于第二个查询,您可以按如下方式移动:$$$(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$$$。