#5046. 「JOISC 2025 Day1」比太郎之旅 2

题目译自 JOISC 2025 Day1 T3 「ビ太郎の旅 2 / Bitaro's Travel 2」

题目描述

JOI 山脉里群山连绵，景色壮丽。这片山脉被划分成一个纵 $H$ 行、横 $W$ 列的网格，纵向与南北平行，横向与东西平行。从北向南第 $i$ ($1 \leq i \leq H$) 行、从西向东第 $j$ ($1 \leq j \leq W$) 列的格子称为格子 $(i, j)$。每个格子里恰好有一座山，格子 $(i, j)$ 上山的山顶的高度是 $T_{i,j}$。

比太郎的跳跃能力为 $L$。当他站在某座山的山顶上时，可以通过高跳移动到另一座山顶。高跳的步骤如下：

1. 从当前山顶垂直向上起跳。如果当前山顶高度为 $x$，比太郎会浮空在高度 $x + L + 0.5$ 的位置。
2. 在保持浮空高度不变的情况下，向东、南、西、北四个方向的相邻格子移动，移动次数可以是 $0$ 次或多次。但移动途中经过的每个格子，其山顶高度必须低于比太郎的浮空高度。
3. 最后降落在当前格子的山顶上。

比太郎计划进行 $Q$ 次旅行。第 $k$ ($1 \leq k \leq Q$) 次旅行的目标是从格子 $(A_k, B_k)$ 的山顶，仅通过高跳到达格子 $(C_k, D_k)$ 的山顶。他想知道每段旅程能否成功，如果能成功，又最少需要几次高跳。因为起跳非常耗费体力，他希望尽量减少高跳次数。

给你 JOI 山脉的地形、比太郎的跳跃能力以及他的旅行计划，你需要编写一个程序，判断每段旅程是否可行，并在可行时计算最少需要的高跳次数。

输入格式

第一行包含三个整数 $H,W,L$。

接下来的 $H$ 行，每行包含 $W$ 个整数 $T_{i,1} \, T_{i,2} , \ldots , T_{i,W}$。

接下来的一行包含一个整数 $Q$。

接下来的 $Q$ 行，每行包含四个整数 $A_i,B_i,C_i,D_i$。

输出格式

输出 $Q$ 行。第 $k$ ($1 \leq k \leq Q$) 行输出第 $k$ 次旅行成功所需的最少高跳次数。若无法成功，则输出 $-1$。

样例 1

输入

2 4 5
1 3 22 1
8 13 6 16
6
1 1 2 2
1 1 1 3
1 1 2 3
1 1 2 4
1 1 1 4
1 1 1 2

输出

3
-1
3
4
4
1

解释
在第 1 次旅行计划中，可以通过以下 3 次高跳，从格子 $(1,1)$ 的山顶移动到格子 $(2,2)$ 的山顶：

• 第 1 次高跳：从格子 $(1,1)$ 的山顶垂直向上跳起，悬浮高度为 $6.5$。移动到格子 $(1,2)$，该格子山顶高度 $3$ 小于 $6.5$，可以移动。在格子 $(1,2)$ 的山顶着陆。
• 第 2 次高跳：从格子 $(1,2)$ 的山顶垂直向上跳起，悬浮高度为 $8.5$。移动到格子 $(1,1)$。移动到格子 $(2,1)$。在格子 $(2,1)$ 的山顶着陆。
• 第 3 次高跳：从格子 $(2,1)$ 的山顶垂直向上跳起，悬浮高度为 $13.5$。移动到格子 $(2,2)$。在格子 $(2,2)$ 的山顶着陆。

无法以少于 3 次高跳完成第 1 次旅行，因此第一行输出 3。

这个样例满足所有子任务的限制。

样例 2

输入

6 5 11
175 100 110 117 158
144 133 123 150 191
167 252 219 181 346
231 241 280 201 209
261 332 325 225 338
269 298 315 291 308
12
1 1 4 2
1 1 1 5
1 1 5 1
1 1 5 4
1 1 3 4
1 1 6 4
1 1 2 5
1 1 3 1
1 1 4 4
1 1 5 5
1 1 6 2
1 1 6 1

输出

8
1
10
6
1
13
2
1
3
19
14
11

这个样例满足所有子任务的限制。

样例 3

输入

4 4 5
53 55 51 49
56 60 89 45
54 57 92 43
96 99 95 92
9
1 4 2 3
4 1 3 2
2 4 2 3
2 1 4 1
1 2 1 1
2 4 1 1
4 1 2 3
3 4 1 1
1 3 1 4

输出

-1
1
-1
-1
1
3
1
4
1

这个样例满足子任务 1,2,4,5 的限制。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq H$
• $1 \leq W$
• $2 \leq H \times W \leq 300000$
• $1 \leq L \leq 10^9$
• $1 \leq T_{i,j} \leq 10^9$ ($1 \leq i \leq H$, $1 \leq j \leq W$)
• $1 \leq Q \leq 300000$
• $1 \leq A_k \leq H$ ($1 \leq k \leq Q$)
• $1 \leq B_k \leq W$ ($1 \leq k \leq Q$)
• $1 \leq C_k \leq H$ ($1 \leq k \leq Q$)
• $1 \leq D_k \leq W$ ($1 \leq k \leq Q$)
• $(A_k, B_k) \neq (C_k, D_k)$ ($1 \leq k \leq Q$)
• 所有输入值均为整数

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
1	10	$H \times W \leq 300$, $Q \leq 150000$
2	20	$H \times W \leq 3000$, $Q \leq 150000$
3		$H \times W \leq 150000$, $Q \leq 150000$, $(A_k, B_k) = (1,1)$ ($1 \leq k \leq Q$)
4	30	$H \times W \leq 150000$, $Q \leq 150000$
5	20	无附加限制