P11985 [JOIST 2025] 比太郎之旅 2 / Bitaro's Travel 2

由于评测机性能差异，本题增加 1 秒时限。

JOI 山脉由许多山峰组成，其地形被表示为一个 $H$ 行 $W$ 列的网格。其中： - 南北方向为纵向，东西方向为横向； - 位于北起第 $i$ 行（$1 \leq i \leq H$）、西起第 $j$ 列（$1 \leq j \leq W$）的单元格记为 $(i, j)$； - 每个单元格中恰好有一座山峰，其高度为 $T_{i,j}$。 比太郎可以通过跳高（high jump）在山峰间移动，其跳跃技能参数为 $L$。具体步骤如下： 1. 上升阶段：从当前山峰上竖直上升。设当前山峰高度为 $x$，则 比太郎会上升到海拔 $x + L + 0.5$ 的位置。 2. 水平移动阶段：在保持海拔不变的前提下，重复向四个相邻方向（上下左右）移动。途经的所有单元格的山峰高度必须低于当前海拔。 3. 降落阶段：最终降落在目标单元格的山峰上。 比太郎计划进行 $Q$ 次旅行。在第 $k$ 次旅行（$1 \leq k \leq Q$）中，他希望**仅通过跳高**从起点 $(A_k, B_k)$ 移动到终点 $(C_k, D_k)$。需要解决的问题： - 判断每次旅行是否可行。 - 若可行，计算所需的最少跳高次数；否则输出 $-1$。

> $H$ $W$ $L$\ > $T_{1,1}$ $T_{1,2}$ $\cdots$ $T_{1,W}$\ > $T_{2,1}$ $T_{2,2}$ $\cdots$ $T_{2,W}$\ > $\vdots$\ > $T_{H,1}$ $T_{H,2}$ $\cdots$ $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$）输出： - 若可行，输出最少跳高次数； - 否则输出 $-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$ 次跳高完成此次旅行，因此第一行输出 `3`。 对于第二次旅行，无法通过跳高到达目标，因此第二行输出 `-1`。 该样例满足所有子任务的限制。 #### 样例 $2$ 解释 该样例满足所有子任务的限制。 ### 数据范围 - $1 \leq H, W$； - $2 \leq H \times W \leq 3\times 10^5$； - $1 \leq L \leq 10^9$； - $1 \leq T_{i,j} \leq 10^9$； - $1 \leq Q \leq 3\times 10^5$； - $1 \leq A_k,C_k\leq H$；$1\le B_k,D_k\le W$； - $(A_k, B_k) \neq (C_k, D_k)$； - 所有输入值为整数。 ### 子任务 | 子任务 | 分数 | $H\times W\le $ | 特殊性质 | | :-: | :-: | :-: | :-: | | $1$ | $10$ | $300$ | | | $2$ | $20$ | $3\times 10^3$ | | | $3$ | $20$ | $150\,000$ | $\text{A}$ | | $4$ | $30$ | $150\,000$ | | | $5$ | $20$ | 无额外限制 | | 特殊性质 $\text{A}$：$\forall 1\le i\le Q$，$(A_i,B_i)=(1,1)$。