SP12958 VPL0_A - Another Gift Problem

Luis 的家人藏起了所有的圣诞礼物，这让他感到十分苦恼。Luis 的家非常富有，他们住在一座拥有很多楼层的摩天大楼中。Luis 准备趁父母外出时，利用电梯偷偷搜寻圣诞礼物的藏匿地点。 Luis 获得了一份大楼地图，并标记了能够找到礼物的地方。大楼的电梯只支持上下移动。你可以假设电梯会随时停在任何楼层并供 Luis 使用，但每次乘坐电梯到达楼层 $A_i$ 都需要花费一个单位的时间，Luis 不可以通过电梯在搜寻过程中离开大楼。 到达某个楼层后，Luis 会从位置 $(0,0)$ 开始寻找礼物，查看完所有房间后，他会返回电梯并继续搜寻。Luis 的目标是找到所有礼物，并且可以忽略没有标记礼物的位置。例如，如果他知道某层没有礼物，可以直接乘坐电梯前往下一地点。以下是关于摩天大楼中 Luis 搜寻的假设： - Luis 的家住在摩天大楼的第 0 层（位置 $(0,0)$）。 - Luis 只能从每层楼的 $(0,0)$ 位置开始使用电梯。 - 第 0 层没有礼物，因为他的父母特别小心地藏礼物。 - Luis 搜寻时不会通过电梯离开大楼。 - 大楼的每一层结构相同，可以用一个 $N \times N$ 的矩阵来表示。 - 电梯可以上行或下行，但不能同时进行。（假设电梯随时运作）。 - 同楼层内，礼物的坐标是唯一的，不会相互重叠。 - Luis 在同一楼层内只能沿水平或垂直方向以单位时间移动。 - 换乘电梯需要一个单位时间，电梯内移动时间忽略不计。 考虑到楼层数、电梯数及其运行层数、礼物的个数和位置，以及每层楼的面积为 $N \times N$，请计算出 Luis 寻找完所有礼物并回到最后一个礼物所在楼层的 $(0,0)$ 所需的最短时间。 保证每个情况都存在至少一个可行方案。

第一行包含一个整数 $T$，表示测试用例数。随后是这 $T$ 个测试用例的具体描述。 每个测试用例以四个整数开始：$M$、$E$、$K$ 和 $N$，分别表示楼层数、电梯数、礼物数和每层楼的大小。 接下来 $E$ 行，每行表示第 $i$ 个电梯上升或下降的楼层数 $E_i$（负数表示下降）。 再接下来 $K$ 行，每行包括三个整数，表示第 $i$ 个礼物所在的楼层 $f$ 及位置 $(r,c)$。 输入必须从标准输入读取。

对于每个测试用例，输出字符串 "Scenario #i: "，其中 $i$ 为测试用例的编号（从 1 开始），接着输出 Luis 搜索完所有礼物所需的最短时间（以单位计算）。 输出必须写入标准输出。

- $1 \leq T \leq 5$ - $1 \leq M \leq 10$ - $1 \leq E \leq 3$ - $1 \leq K \leq 2$ - $1 \leq N \leq 1$ 例如给定输入： ``` 5 5 1 1 1 1 3 0 0 5 3 1 1 1 4 -1 3 0 0 5 1 2 1 1 2 0 0 4 0 0 10 3 2 1 1 8 -2 4 0 0 6 0 0 5 3 3 5 1 2 -1 2 1 3 2 4 1 2 3 4 ``` 样例输出为： ``` Scenario #1: 3 Scenario #2: 2 Scenario #3: 4 Scenario #4: 3 Scenario #5: 17 ``` **例外说明** 在最后一个用例中， Luis 从第 0 层出发，乘电梯到第 2 层。假设在第二层上的三个礼物的坐标分别为 A=$(1,3)$，B=$(4,1)$，C=$(3,4)$。Luis 可以通过多种路径收集这些礼物：A->B->C、B->C->A、C->A->B、C->B->A、A->C->B 或 B->A->C。然而，最短路径是 B->A->C，接着返回原点 $(0,0)$，总计 16 步，再���上电梯的一个单位时间，总共为 17 单位时间。 **本翻译由 AI 自动生成**