← 返回题目列表

AtCoder · joisp2025_c

C. 比特太郎的旅行 2

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

配点: 100 点

JOI山脉中排列着许多山脉。 JOI山是垂直的 H 行,横 W 表示为由列分隔的网格, 垂直方向平行于南北方向,水平方向平行于东西方向。 从北方 i 行目 (1 \leqq i \leqq H),从西边 j 列目 (1\leqq j\leqq W) 它被称为 (i, j) 。 1 正是 1 有两座山; 鳟鱼 (i, j) 中山峰的高度为 T_{i, j} 是。

Bitaro的跳跃力是 L 。当Bitaro在山顶的时候, 跳高 你可以通过 移动到另一座山的山顶。 跳高 你可以通过 是指按顺序执行以下操作。

  • 从你当前所在的山顶直接跳上去。您当前所在山峰的高度 x ,Bitaro是那个正方形的高度 浮动在 x + L + 0.5 的位置。
  • 移动到与北、南、东或西相邻的正方形,不改变高度。 重复至少 0 次。对于此时访问的所有方格来说,这些方格中山峰的高度一定低于Bitaro漂浮的高度。
  • 降落在你当前所在广场的山顶上。

比特太郎是 我正在计划一次 Q 旅行。 k 回目 (1\leqq k \leqq Q)的行程如下: 鳟鱼 从 (A_{k}, B_{k}) 山顶 鳟鱼 目标是仅通过跳高到达 (C_{k}, D_{k}) 的山顶。 我想知道Bitaro能否让这次旅行成功。另外,由于跳高动作需要很大的体力, 我想知道成功旅行所需的最少跳高次数。

JOI 当给出有关山脉、Bitaro的跳跃能力和Bitaro的旅行计划的信息时, 对于每一个计划, 编写一个程序来确定这次旅行是否会成功,如果成功,请找出所需的最少跳高次数。 输出


入力

输入是按以下格式从标准输入给出的。

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\leqq k \leqq Q)有 k 打印成功完成第一次行程所需的最少跳高次数。 但如果旅行不成功,-1 。

制約

  • 1\leqq H.
  • 1\leqq W.
  • 2\leqq H\times W \leqq 300\,000.
  • 1\leqq L\leqq 10^{9}.
  • 1\leqq T_{i, j}\leqq 10^{9} (1\leqq i\leqq H,1\leqq j\leqq W).
  • 1\leqq Q \leqq 300\,000.
  • 1\leqq A_{k} \leqq H (1\leqq k \leqq Q).
  • 1\leqq B_{k} \leqq W (1\leqq k \leqq Q).
  • 1\leqq C_{k} \leqq H (1\leqq k \leqq Q).
  • 1\leqq D_{k} \leqq W (1\leqq k \leqq Q).
  • (A_{k}, B_{k})\neq (C_{k}, D_{k}) (1\leqq k \leqq Q).
  • 所有输入值都是整数。

小課題

  1. (10 点) H\times W \leqq 300,Q\leqq 150\,000.
  2. (20 点) H\times W \leqq 3\,000,Q\leqq 150\,000.
  3. (20 点) H\times W \leqq 150\,000,Q\leqq 150\,000,(A_{k}, B_{k}) = (1, 1) (1\leqq k \leqq Q).
  4. (30 点) H\times W \leqq 150\,000,Q\leqq 150\,000.
  5. (20 点)没有额外的限制。

入力例 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

出力例 1

3
-1
3
4
4
1

1 当计划我的第二次旅行时,我想做如下所示的跳高。 3 通过转动,您可以 (1, 1) 山顶的鳟鱼 (2, 2) 前往山顶。

  • 1 第二次跳高
    • 质量 从 (1, 1) 的山顶直接跳上去。此时Bitaro的身高为 移至 6.5 是。
    • 质量 从 (1, 2) 。鳟鱼 (1, 2) 处的山的高度 它比 3 是 6.5 小并且可以移动。 降落在
    • 质量 从 (1, 2) 山顶。 移至
  • 2 第二次跳高
    • 质量 从 (1, 2) 的山顶直接跳上去。此时Bitaro的身高为 移至 8.5 是。
    • 质量 从 (1, 1) 。
    • 质量 从 (2, 1) 。
    • 质量 从 (2, 1) 山顶。 移至
  • 3 第二次跳高
    • 质量 从 (2, 1) 的山顶直接跳上去。此时Bitaro的身高为 移至 13.5 是。
    • 质量 从 (2, 2) 。
    • 质量 从 (2, 2) 山顶。 移至

跳高次数 少于 3 次 1 我无法让我的第二次旅行成功,所以1 在线 3 。

2 我无法让我的第二次旅行成功,所以2 在线 -1 。

此输入示例满足所有子任务约束。


入力例 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

出力例 2

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

出力例 3

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

此输入示例是一个小作业。 1,2,4,5 满足约束。