SAPO 2019（南非计算机奥林匹克）决赛第二日的题目 D：《我的世界模拟器》（Minecraft Simulator）。

---

题目 D：Minecraft 模拟器 (Minecraft Simulator)

项目	限制条件
输入文件	input_*.txt
输出文件	output_*.txt
时间/内存限制	无限制（提交答案题）
总分	100 分（共 25 组测试用例，每组 4 分）

题目背景

是时候玩 Minecraft 了！受某位知名博主启发，你决定亲自尝试在 Minecraft 中建造宏伟的工程。

核心规则

1. 世界表示：世界由 3D 坐标 $(x, y, z)$ 组成，每个点要么是空的，要么有一种类型的方块 $t$。
2. 角色状态：Steve 占据 $1 \times 1 \times 2$ 的空间。要站在 $(x, y, z)$，则 $(x, y, z)$ 和 $(x, y, z+1)$ 都必须为空，且 $(x, y, z-1)$ 必须有实体方块（作为地面）。
3. 物品栏：初始为空，但容量无限，可以装载无限数量的各类方块。

可执行动作

• 移动 (Move)：向东南西北（$\pm x, \pm y$）移动一格。
  • 指令：move north, move south, move east, move west。
  • 限制：目标位置及其上方一格必须为空。
• 跳跃 (Jump)：向四个方向跳跃，坐标 $z$ 增加 1。

  • 指令：jump north, jump south, jump east, jump west。

  • 

  • 限制：除了目标位置的 $1 \times 1 \times 2$ 空间，当前位置上方第二格 $(x, y, z+2)$ 也必须为空。

• 挖掘 (Mine)：移除 $(x, y, z)$ 处的方块并加入物品栏。

  • 指令：mine x y z。

  • 限制：只能挖掘与 Steve 相邻（面相邻或边相邻）的方块。

  • 

  • 挖掘规则：

    1. A类（面相邻）：Steve 前后左右及足底共 10 个方块，随时可挖。
    2. B类（边相邻）：必须与该边相邻的某个 A 类方块是空的，才能挖掘 B。
• 放置 (Place)：将物品栏中的方块 $t$ 放在 $(x, y, z)$。
  • 指令：place x y z t。
  • 限制：相邻规则同挖掘。此外，目标位置的 6 个相邻位置中必须至少有一个已存在的实体方块。
• 跳跃并放置 (Jump and place)：向上跳起并在原脚下位置放一个方块。
  • 指令：jump and place t。
  • 限制：$(x, y, z+2)$ 必须为空。

特殊机制：自动坠落

每执行完一条指令，Steve 会自动向下掉落（$z$ 坐标减小），直到踩到实体方块。

• 注意：如果一次坠落高度超过 10 格，执行立即停止，该用例得 0 分。

输入格式

1. 第一行：x0 y0 z0（初始出生点）。
2. 第二行：$N$（世界中现有方块数量）。
3. 接下来的 $N$ 行：xi yi zi ti（现有方块的坐标和类型）。
4. 下一行：$M$（你需要放置的方块数量）。
5. 接下来的 $M$ 行：xi yi zi ti（任务要求放置的方块坐标和类型）。

输出格式

本题为仅输出题。你需要针对每个 input_*.txt 提交对应的 output_*.txt。 每行包含一条指令。每个文件最多处理 $10^6$ 条指令。

评分标准

得分计算方式：$4 \times (\text{成功放置的方块数} / M)$。

• 测试点分布：
  • 1-3：坐标范围极小 ($<5$)。
  • 7-10：不需要跳跃或坠落。
  • 20-22：不需要额外垫方块（搭脚手架）。
  • 23-25：无限制。

---

样例说明（第一个例子简述）

• 场景：Steve 站在 $3 \times 3$ 的草地上，角落有一个石块。
• 任务：把这个石块移到对角线的另一端。
• 操作序列：
  1. move south（走向石块）
  2. mine 0 0 1（挖掉石块）
  3. move north
  4. move north（走到目标点附近）
  5. place 2 2 1 2（放置石块）

---

非常抱歉！由于之前的格式排版问题，样例部分显示得比较乱。这道题是提交答案题，理解样例中指令的执行过程对写代码（模拟器）至关重要。

以下我为你重新整理了 样例 1 的完整内容，并补充了详细的步骤拆解，方便你对照配图。

---

📝 样例 1 详解

1. 输入数据 (input_1.txt)

1 1 1         // Steve 的出生点 (x0, y0, z0)
10            // 世界中现有 10 个方块
0 0 0 1       // 坐标(0,0,0) 类型1 (草方块)
0 1 0 1       // 坐标(0,1,0) 类型1
0 2 0 1       // ... 这是一个 3x3 的平台 ...
1 0 0 1
1 1 0 1
1 2 0 1
2 0 0 1
2 1 0 1
2 2 0 1
0 0 1 2       // 坐标(0,0,1) 类型2 (石块) - 这是我们要挖的目标
1             // 任务：需要放置 1 个方块
2 2 1 2       // 目标：在 (2,2,1) 放置类型2 (石块)

2. 输出指令 (output_1.txt)

move south    // 向南移到 (1, 0, 1)
mine 0 0 1    // 挖掘相邻的石块 (0,0,1)，石块进入物品栏
movenorth     // 回到 (1, 1, 1)
movenorth     // 移动到 (1, 2, 1)
place 2 2 1 2 // 在相邻位置 (2,2,1) 放置类型2方块

---

🔍 关键规则图解建议

如果你在配图，以下是几个核心逻辑的“视觉要点”：

1. Steve 的空间占用

Steve 占据 两格高。

• 如果 Steve 在 $(1, 1, 1)$，那么 $(1, 1, 1)$ 和 $(1, 1, 2)$ 必须是空气。
• 他的脚下 $(1, 1, 0)$ 必须有实体方块支撑。

2. 挖掘与放置的 A/B 范围

这是最容易出错的地方，建议按照以下偏移量画图：

• A 类（面相邻 - 随时可操作）:
  • 前后左右（两层高）：$(x \pm 1, y, z), (x \pm 1, y, z+1), (x, y \pm 1, z), (x, y \pm 1, z+1)$
  • 头顶与脚底：$(x, y, z-1), (x, y, z+2)$
• B 类（边相邻 - 需 A 类为空）:
  • 例如：$(x+1, y+1, z)$。要挖它，必须 $(x+1, y, z)$ 或 $(x, y+1, z)$ 其中一个是空气。

3. 自动坠落机制 (Auto-fall)

每一步指令后，系统检查 Steve 脚下。

• 合法：下方 1-10 格内有方块，Steve 自动掉落到该方块上方。
• 失败：下方超过 10 格都是空气，Steve 摔死，得 0 分。

---

这份翻译涵盖了原文档中第 2 到第 4 个示例的逻辑解析，这些例子展示了“垫脚石”和“跳跃放置”等进阶操作。

---

样例说明（续）

在第二个示例中，Steve 需要向西跳跃（jump west）才能触及剩余的唯一一个石块。接着，他可以向右移动（这会导致他自动向下坠落一格），然后再次向右跳跃，最后将石块放置在右侧。

在第三个示例中，世界上只有两块草方块，分别位于 $(0,0,0)$ 和 $(1,0,0)$。Steve 的目标是在位置 $(2,1,0)$ 放置一个草方块。达成目标的唯一途径是：先在位置 $(2,0,0)$ 放置一个中转草方块（作为支点），然后才能在上方放置最终的目标方块。

在第四个示例中，Steve 挖掘了位于 $(-1,0,0)$ 和 $(1,0,0)$ 处的两个草方块（这两个方块就在他当前站立的方块旁边）。随后，Steve 执行了“跳跃并放置”（jump and place）指令，在 $(0,0,1)$ 位置放置了一个草方块。这使得 Steve 的高度足以够到并把最后的草方块放在要求的 $(0,0,4)$ 位置。

---

💡 核心逻辑划重点：

1. 中转方块 (Intermediary Blocks)：第三个例子提醒我们，有时候为了放一个高处的方块，你必须先放一个低处的方块作为“地基”。
2. 跳跃放置 (Towering)：第四个例子演示了 Minecraft 中经典的“原地拔高”技巧，这在处理 $z$ 轴较高的任务时非常有用。
3. 挖掘现有资源：如果物品栏没方块了，记得先挖掘周围不用的方块（比如脚下的平台边缘）来充当建筑材料。

---