AT_joisp2025_c ビ太郎の旅 2 (Bitaro's Travel 2)

JOI 山脉上有许多山峰排列成行。JOI 山脉可以表示为一个被划分为 $H$ 行 $W$ 列的网格，纵向与南北方向平行，横向与东西方向平行。从北往南第 $i$ 行（$1 \leq i \leq H$），从西往东第 $j$ 列（$1\leq j\leq W$）的格子被称为格子 $(i, j)$。每个格子中正好有一个山峰，格子 $(i, j)$ 的山顶高度为 $T_{i, j}$。 比太郎的跳跃力为 $L$。比太郎在山顶时，可以通过**高跳**移动到另一个山顶。**高跳**是指顺序执行以下操作： - 从当前位置山顶向上跳跃。若当前山顶高度为 $x$，比太郎将漂浮到高度 $x + L + 0.5$ 的位置。 - 可以任意次（包括 $0$ 次）以相同高度水平移动到东西南北相邻的格子。此移动过程中，经过的所有格子上的山顶高度都必须严格小于比太郎漂浮的高度。 - 在当前格子的山顶落地。 比太郎计划进行 $Q$ 次旅行。第 $k$ 次（$1\leq k\leq Q$）旅行的内容是：仅通过高跳，从格子 $(A_{k}, B_{k})$ 的山顶，移动到格子 $(C_{k}, D_{k})$ 的山顶。比太郎想知道每次旅行能否成功，如果成功，还想知道所需的高跳次数的最小值。 给定 JOI 山脉各山的高度、比太郎的跳跃力以及所有旅行计划，请你判断每次旅行是否可达，若可以还要输出所需高跳次数的最小值。 ---

输入从标准输入按下列格式给出。 > $H$ $W$ $L$ $T_{1,1}$ $T_{1,2}$ $\ldots$ $T_{1,W}$ $T_{2,1}$ $T_{2,2}$ $\ldots$ $T_{2,W}$ $\vdots$ $T_{H,1}$ $T_{H,2}$ $\ldots$ $T_{H,W}$ $Q$ $A_1$ $B_1$ $C_1$ $D_1$ $A_2$ $B_2$ $C_2$ $D_2$ $\vdots$ $A_Q$ $B_Q$ $C_Q$ $D_Q$

请输出 $Q$ 行。对于第 $k$ 行（$1\leq k\leq Q$），输出使得第 $k$ 次旅行成功所需的最小高跳次数。若该旅行无法成功，则输出 `-1`。

### 子任务 1.（$10$ 分）$H\times W \leq 300$，$Q\leq 150\,000$。 2.（$20$ 分）$H\times W \leq 3\,000$，$Q\leq 150\,000$。 3.（$20$ 分）$H\times W \leq 150\,000$，$Q\leq 150\,000$，$(A_{k}, B_{k}) = (1, 1)$（$1\leq k\leq Q$）。 4.（$30$ 分）$H\times W \leq 150\,000$，$Q\leq 150\,000$。 5.（$20$ 分）无额外约束。 --- ### 样例解释 1 对于第 $1$ 次旅行，可以如下完成 $3$ 次高跳，从 $(1, 1)$ 的山顶到 $(2, 2)$ 的山顶。 - 第 $1$ 次高跳： - 从 $(1, 1)$ 山顶跳起，此时比太郎高度为 $6.5$。 - 移动到 $(1, 2)$。$(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$ 次旅行，因此第 $1$ 行输出 $3$。 第 $2$ 次旅行无法成功，因此第 $2$ 行输出 `-1`。 该输入满足所有子任务的约束。 --- ### 样例解释 2 该输入满足所有子任务的约束。 --- ### 样例解释 3 该输入满足子任务 $1,2,4,5$ 的约束。 # 数据范围与提示 - $1\leq H$。 - $1\leq W$。 - $2\leq H\times W\leq 300\,000$。 - $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 300\,000$。 - $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$）。 - 所有输入均为整数。 由 ChatGPT 5 翻译