描述
## 题目背景
某研究基地内部有一座立体建筑。建筑中的机器人携带一盏亮度可调的探照灯，需要在不同房间之间完成若干次运输任务。
## 题目描述
建筑由 $X\times Y\times Z$ 个房间组成。房间用三维坐标 $(x,y,z)$ 表示，其中 $1\le x\le X$、$1\le y\le Y$、$1\le z\le Z$。每个房间只与前后、左右、上下六个方向上的房间相邻。
房间 $(x,y,z)$ 的探照灯最高允许亮度为 $A[x][y][z]$。机器人携带一盏可调节亮度的探照灯，当前亮度为 $b$。
机器人可以进行以下操作：
- 在当前房间将探照灯亮度提高 $1$ 或降低 $1$，代价为 $1$；
- 机器人在房间内停留或调整亮度时，亮度始终为正整数，且不能超过当前房间的最高允许亮度；
- 通过房门进入六连通相邻房间，代价为 $0$。通过房门时亮度保持不变，因此亮度必须同时不超过离开房间和进入房间的最高允许亮度。
给定 $Q$ 次相互独立的运输任务。每次任务给出起点房间、起始亮度、终点房间和目标亮度，请计算完成任务所需的最小亮度调整代价。
输入
第一行包含三个整数 $X,Y,Z$。
接下来给出 $X$ 个部分。第 $x$ 个部分包含 $Y$ 行，每行包含 $Z$ 个整数；其中第 $x$ 个部分第 $y$ 行第 $z$ 个整数为 $A[x][y][z]$。
下一行包含一个整数 $Q$。
接下来 $Q$ 行，每行包含八个整数：
```text
x1 y1 z1 b1 x2 y2 z2 b2
```
表示机器人从房间 $(x_1,y_1,z_1)$ 的亮度 $b_1$ 出发，最终到达房间 $(x_2,y_2,z_2)$，且亮度为 $b_2$。
保证：
$$
\begin{aligned}
1&\le b_1\le A[x_1][y_1][z_1],\\
1&\le b_2\le A[x_2][y_2][z_2].
\end{aligned}
$$
每次运输任务相互独立，前一次任务结束时机器人的位置和亮度不会影响下一次任务。
输出
输出 $Q$ 行，每行一个整数，表示对应任务的最小亮度调整代价。
样例
- 复制
- 复制
提示
## 样例解释
以第 1 次任务为例。起点房间 $(1,1,1)$ 的上限为 $7$，终点房间 $(2,2,2)$ 的上限为 $9$。从起点离开时，若想保持亮度至少为 $6$，无论先走向哪个相邻房间都会超过该相邻房间的上限；能够贯穿一条路径的最大亮度为 $5$。因此机器人先将亮度从 $7$ 调到 $5$，到达终点后再将亮度从 $5$ 调到 $8$，总代价为
$$
(7-5)+(8-5)=5
$$
这也说明答案不一定等于起止亮度差 $\lvert 7-8\rvert=1$，还会受到路径上允许亮度的最小值影响。
第 2 次任务的起点上限本身只有 $3$，所以机器人必须以不超过 $3$ 的亮度离开起点，最后再在终点调到 $8$，总代价为 $5$。第 3 次任务不需要移动，只需把亮度从 $4$ 调到 $1$，代价为 $3$。
第 $4$ 次任务中，起点与终点相邻，机器人保持亮度 $5$ 移动到终点后，再将亮度调至 $8$，代价为 $3$。
## 数据范围与测试点
本题包含 $20$ 个测试点，每个测试点 $5$ 分，测试点之间独立计分。
对于所有测试点，均保证以下基本范围成立：
- $1\le X,Y,Z$；
- $X\times Y\times Z\le 2\times 10^{5}$；
- $1\le Q\le 2\times 10^{5}$；
- $1\le A[x][y][z]\le 10^{6}$；
- $1\le b_1,b_2\le 10^{6}$。
在此基础上，各测试点的额外限制如下。表中的“—”表示除上述通用数据范围外，没有额外限制。
| 测试点编号 | $X,Y,Z$ | $Q$ | $A[x][y][z]$ | 分值 |
|:---:|:---:|:---:|:---:|:---:|
| 1 | $X=Y=1,\ Z\le 30$ | $\le 500$ | — | $5$ |
| 2 | $X=Y=1,\ Z\le 2\times 10^5$ | $\le 2\times 10^5$ | — | $5$ |
| 3 | $Z=1,\ X\times Y\times Z\le 10^3$ | $\le 5\times 10^3$ | — | $5$ |
| 4 | $Z=1,\ X\times Y\times Z\le 2\times 10^4$ | $\le 3\times 10^4$ | — | $5$ |
| 5 | $X\times Y\times Z\le 10^3$ | $\le 5\times 10^3$ | — | $5$ |
| 6 | $X\times Y\times Z\le 10^3$ | $\le 5\times 10^3$ | $A[x][y][z]=100$ | $5$ |
| 7 | $X=Y=Z=1$ | $\le 5\times 10^3$ | — | $5$ |
| 8 | $X\times Y\times Z\le 2\times 10^4$ | $\le 3\times 10^4$ | — | $5$ |
| 9 | $X=20,\ Y=20,\ Z=10$ | $\le 10^4$ | $\begin{cases}2,&x=11\\10^6,&x\ne 11\end{cases}$ | $5$ |
| 10 | $X=30,\ Y=30,\ Z=10$ | $\le 10^4$ | $\begin{cases}2,&x=16\\10^6,&x\ne 16\end{cases}$ | $5$ |
| 11 | $X=Y=Z=20$ | $\le 10^4$ | $A[x][y][z]\in\{1,10^6\}$ | $5$ |
| 12 | $X=40,\ Y=50,\ Z=50$ | $\le 2\times 10^5$ | — | $5$ |
| 13 | $X=40,\ Y=100,\ Z=50$ | $\le 2\times 10^5$ | — | $5$ |
| 14 | $X=50,\ Y=80,\ Z=50$ | $\le 2\times 10^5$ | $\begin{cases}2,&x=26\\10^6,&x\ne 26\end{cases}$ | $5$ |
| 15 | $X=40,\ Y=50,\ Z=100$ | $\le 2\times 10^5$ | $A[x][y][z]=10^6$ | $5$ |
| 16 | $X=50,\ Y=80,\ Z=50$ | $\le 2\times 10^5$ | $\begin{cases}10^6,&x\ne 26\lor(y,z)=(1,1)\\1,&x=26\land(y,z)\ne(1,1)\end{cases}$ | $5$ |
| 17 | $X=50,\ Y=80,\ Z=50$ | $\le 2\times 10^5$ | — | $5$ |
| 18 | $X=80,\ Y=50,\ Z=50$ | $\le 2\times 10^5$ | $\begin{cases}5\times10^5,&x=41\\10^6,&x\ne 41\end{cases}$ | $5$ |
| 19 | $X=Y=1,\ Z\le 10^5$ | $\le 2\times 10^5$ | — | $5$ |
| 20 | $X=40,\ Y=50,\ Z=100$ | $\le 2\times 10^5$ | — | $5$ |
关注我们
