97315 - 亮度（brightness）

讨论

统计

通过次数

提交次数

旧版界面

时间限制 : 2 秒

内存限制 : 512 MB

题目背景

某研究基地内部有一座立体建筑。建筑中的机器人携带一盏亮度可调的探照灯，需要在不同房间之间完成若干次运输任务。

题目描述

建筑由 $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$ 行，每行包含八个整数：

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$ 行，每行一个整数，表示对应任务的最小亮度调整代价。

样例

输入

2 2 2
7 5
4 6
3 8
2 9
4
1 1 1 7 2 2 2 8
2 1 1 3 2 2 2 8
1 2 1 4 1 2 1 1
1 1 2 5 2 1 2 8

输出

提示

样例解释

以第 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$

来源

2026第五届青少年编程挑战精英赛