LibreOJ

2258 「SNOI2017」魔塔

题目描述

1 游戏概述

魔塔是 RPG（Role Playing Game，角色扮演游戏）的代表。在这款游戏中，你需要操作勇士与怪物战斗，并用获取的金钱提升自己的能力，从而挑战更强的怪物。而最终的目标，则是营救公主。
与传统的魔塔相比，本题去除了大量的设定，只留下了一些最基本的元素。

2 场地

游戏的场地为一个矩形，被划分为 $M\times N$ 个小方格。
小方格可能是空地，也可能有人或怪物。下面是所有可能出现的状态，用一个字母表示：
a：adventurer，表示勇士的初始位置；
n：表示NPC；
p：princess，表示公主；
m：monster，表示怪物；
o：表示墙壁；
.：表示空地。
NPC、公主、怪物、墙壁均不可穿越，勇士只能向上下左右四个方向相邻（注：之后所有的“相邻”都表示四个方向）的空地移动。移动后，空地与勇士的位置交换。 怪物是唯一可以改变的地形；怪物被消灭后，会变为空地。

3 战斗

触发战斗的条件是勇士所在的位置与怪物相邻。
勇士与怪物均拥有三个属性：生命值、攻击力、防御力。怪物的属性会在游戏开始时给出，且不会改变；而勇士可以通过商店进行购买，同时生命值也会因为战斗而下降。
每一场战斗由勇士先进行攻击，之后怪物攻击，之后勇士攻击，之后怪物攻击……如此循环。
每次攻击所造成的伤害为 $\max($ 攻击者攻击力 $-$ 对方防御力 $,0)$，对方的生命值会扣减这个数值。
任何一方生命值小于等于 $0$ 将会死亡，战斗结束。

战斗举例 1：

勇士 生命值 10 攻击力 5 防御力 2
怪物 生命值 10 攻击力 3 防御力 1
勇士先进行攻击，对怪物造成 $5-1=4$ 点伤害，怪物生命值为 6；
怪物进行攻击，对勇士造成 $3-2=1$ 点伤害，勇士生命值为 9；
勇士进行攻击，对怪物造成 $5-1=4$ 点伤害，怪物生命值为 2；
怪物进行攻击，对勇士造成 $3-2=1$ 点伤害，勇士生命值为 8；
勇士进行攻击，对怪物造成 $5-1=4$ 点伤害，怪物生命值为 -2，死亡！
在这场战斗中，勇士消灭怪物，损失了 2 点生命值。

战斗举例 2：

勇士 生命值 10 攻击力 5 防御力 6
怪物 生命值 10 攻击力 5 防御力 2
由于怪物对勇士造成的伤害为 0，而勇士对怪物造成的伤害不为 0，故结果为勇士消灭怪物，损失 0 点生命值。

当勇士死亡，或战斗进入无限循环（两方伤害均为 0）时，均为勇士失败，游戏立即结束。

4 商店

勇士可以进入商店购买物品。商店可以在任何时候使用，与勇士当前位置无关。
勇士拥有初始金钱，同时每个怪物被消灭时也会掉落一定的金钱。
在商店里，属性以物品的形式呈现。每个物品包括了价格、生命值、攻击力、防御力、存量几个属性。
勇士支付对应的价格后，即可获得这一商品的生命值、攻击力、防御力，并直接加到自己的属性上。此外，勇士够买这一商品的次数不能超过其存量。

5 对话

触发对话的条件是勇士与 NPC 或公主相邻。
勇士可以与场地中的 NPC 对话，NPC 会给勇士人生的经验。
这些对话在大多数时候只起到为 RPG 渲染环境的作用，但有时，这些对话对过关有提示作用。极少数情况下，NPC 的对话会与游戏规则抵触，此时以 NPC 对话内容为准。
最后，勇士可以与公主对话，对话之后营救成功，游戏立即结束，公主同样会留下一段感谢的话。

6 目标

游戏的目标是，在营救公主时，保留尽可能多的生命值。生命值会按照一定的规则，转化为公主的爱意值，也即 1 到 10 之间的整数。
若未成功营救公主（战斗时死亡、无限循环，操作不合法等），则算作未完成游戏目标，爱意值将被记为 0。

输入格式

这是一道提交答案型试题，你不需要提交你的源程序。你只需根据给出的 10 个输入文件，使用适当的方法编写 10 个输出文件并提交。
所有的输入文件 mota1.in ~ mota10.in 已在对应的目录下。

输入文件 motaX.in 的第一行是两个正整数 $N$ 与 $M$，表示场地的宽与长。
接下来 $N$ 行，每行 $M$ 个字符，为“场地”中所对应的字符，中间没有空格。这些字符中，保证勇士 a 与公主 p 恰好出现一次。
接下来一行包括四个空格隔开的整数 $\text{Cash}, \text{Health}, \text{Atk}, \text{Def}$，分别表示勇士的初始金钱、初始生命值、初始攻击力、初始防御力。
接下来一行为一个整数 $P$，表示怪物的数量。
接下来 $P$ 行，每行有六个空格隔开的整数 $\text{cash},\text{hp},\text{atk},\text{def},x,y$，描述了一只怪物，分别表示击杀怪物获得的金钱、怪物生命值、怪物的攻击力、怪物的守备力、怪物的行坐标、怪物的列坐标（也即：怪物在第 $x$ 行，第 $y$ 列）。保证场地中的每个 m 所对应的坐标，均在本段恰好出现一次。
接下来一行为一个整数 $R$，表示商店中物品的种类。
接下来 $R$ 行，每行有五个空格隔开的整数 $\text{cash},\text{hp},\text{atk},\text{def},\text{num}$，描述了一件物品，分别表示商品的价格，购买之可以获得的生命值、攻击力、防御力，以及商品存量。
输入文件结束。

输出格式

**对应每一个输入文件，你需要编写 `mota1.out` ~ `mota10.out` 放在对应的目录下。** 你的输出需要包括若干行，每行描述了一个操作。下方列出了可能的操作，实际使用时，需要用对应的数字替换尖括号里（含尖括号本身）的内容： `MOVE ` 内容：表示移动到坐标为第 $X$ 行，第 $Y$ 列的地点。允许在一次操作中进行多次移动，从而直接移动到目标点。 条件：$(X,Y)$ 必须为空地，且可以从勇士所在位置经过若干次向相邻方格的移动达到。 `ATTACK ` 内容：对第 $X$ 行，第 $Y$ 列的怪物发起攻击。结算勇士各项属性及金钱变化，并进行死亡判定。 条件：$(X,Y)$ 必须为怪物，且勇士所处位置与其相邻。 `TALK ` 内容：与第 $X$ 行，第 $Y$ 列的 NPC 或公主进行对话。对话的结果会输出到屏幕。如果对话的是公主，则游戏结束，此行之后的内容会被忽略。 条件：$(X,Y)$ 必须为 NPC 或公主，且勇士所处位置与其相邻。 `BUY ` 内容：购买第 $S$ 种商品 $T$ 件。结算勇士各项属性及金钱变化。 条件：购买商品后自己金钱不小于 0。 你的输出不能超过 100000 行。

样例

勇士向 $(1,1)$ 移动后，攻击 $(1,2)$ 处的怪物。 勇士的属性为 $(10,5,2)$，怪物的属性为 $(10,3,1)$。这是战斗系统中的例子，勇士损失 $2$ 点生命，消灭怪物获得 $10$ 金钱。此时，$(1,2)$ 变为空地。 勇士购买 $3$ 号商品 $2$ 件，也即 $4$ 点防御，此时属性为 $(10,5,6)$。 勇士向 $(1,2)$ 移动后，攻击 $(1,3)$ 处的怪物。这也是战斗系统中的例子，勇士无伤消灭怪物，获得 $10$ 金钱。 勇士购买 $1$ 号商品 $1$ 件，也即 $100$ 点生命。此时勇士生命为 $108$。 勇士向 $(1,3)$ 移动后与位于 $(1,4)$ 的公主对话，游戏结束。 可以证明，$108$ 是勇士通关时可能的最大生命值。

数据范围与提示

#### 数据范围 $1 \leq N,M \leq 1000$；$0 \leq R \leq 1000000$； 其它提及的参数均为整数且不超过 $10^{12}$。 #### 评分方法 我们提供了 `mota1.ans` ~ `mota10.ans` 这十个文件，分别对应了计算**爱意值**的参数。每个文件包含 9 个空格隔开的整数，分别为 $a_{10},a_9,…,a_2$。我们约定 $a_1=0$。 对于每个测试点，设勇士最后的**生命值**为 $H$，形式化地，**爱意值**为满足 $H\geq a_i$ 的最大 $i$ 值。 你的得分为 10 个测试点中，爱意值的总和。 #### 如何测试你的输出 我们提供了 `motacheck.exe` 这个程序来测试你的输出。考虑到大多数选手的情况，这里只提供 Windows 下的测试方法。 使用时，请确保 `mota1~10.in`，`mota1~10.out`，`mota1~10.ans`，`motacheck.exe` 均在同一目录下。 此时运行 `motacheck.exe`，会产生一个文件 `mota.log`，表示了测试结果。 这个文件会包括 11 行，其中，前 10 行分别表示每个测试点的爱意值，而最后一行为你的总分。 #### checker 的其它用法 `motacheck.exe` 还有其它用途。**请注意：这是观看 NPC 对话的必备方式**。 在 Windows 下，按住 Shift 后右键点击当前目录下的空白处，选择“在此处打开命令窗口”；或在命令提示符下输入“`cd \对应目录`”，进入对应目录。 例如，本题所有文件均在目录 `E:\ABC\mota\` 下，则你需进行的操作是： 打开 `E:\ABC\mota\`，右键单击空白处并选择“在此处打开命令窗口” 或 输入 `E:` 回车 输入 `cd \ABC\mota` 回车 或 输入 `cd /d E:\ABC\mota` 回车 此时屏幕上会显示 `E:\ABC\mota> `，这表明已经进入对应目录。 你可以输入 **`motacheck X`** 其中 $X$ 为任意正整数，即可测试第 $X$ 组数据。 例如，输入 `motacheck.exe 1` 回车 表明需要测试第一组数据。 此时，所有与 NPC 和公主的对话会**以中文**显示在屏幕上。 如果你的输出不合法，则会**以中文**输出错误内容，格式通常为： `测试终止于第 L 行，错误 XXX：YYYYYYYYY` 这表示错误发生在你的输出的第 $L$ 行，$\text{XXX}$ 为错误编号，$\text{YYYYYYYY}$ 为错误内容。 你也可以将 $X$ 定义为大于 $10$ 的数，这可以帮助你自己编一些数据来测试你的程序的正确性。 使用自编的数据时，请保证： `.in`，`.out`，`.ans` 文件均存在，且满足上面的输入格式。我们不检查 `.in` 与 `.ans` 的格式，如果输入错误可能不会有报错信息。 注意：只有原始的 10 组数据可以触发 NPC 对话，自编的数据中与 NPC 对话会进入时间的裂缝，NPC 无法提供有效对话。 此外，我们提供了一些可选的参数： **`-b`** 屏蔽与 NPC 和公主的对话，并将分数单独显示。 **`-d <文件名>`** 开启调试模式。程序将在每一步输出勇士的行坐标、列坐标、生命值、攻击力、防御力、金钱到文件中，如文件已存在则覆盖。如不指定文件名，则输出到 `debug.log`。 **`-h`** 显示此帮助。 **`-o <文件名>`** 将对话内容输出到文件中。如不指定文件名，则输出到 `output.log`。 **`-p <文件名>`** 评测模式，此参数替代 $X$，且覆盖其它参数。将选手的 10 组输出变为评测机可以接受的形式，保存为 `cpp` 文件。如不指定文件名，则输出到 `mota.cpp`。 **`-s <文件名>`** 简化模式，此参数替代 $X$，且覆盖其它参数。直接向文件输出选手的得分（与无参数相同）。如不指定文件名，则输出到 `mota.log`。 形式化地，`motacheck` 的使用方式为： `motacheck [ X | -p [] | -s [] ] [ -b ] [ -d [] ] [ -o [] ] ` # 注意：由于 SNOI 只提供了一个 checker 的 exe 文件，且其内容十分丰富难以仿制，故我们无法在线上评测。请您自行使用 checker 进行评测。

样例

样例输入 1

3 4
.mmp
.ooo
a...
0 10 5 2
2
10 10 3 1 1 2
10 10 5 2 1 3
3
10 100 0 0 1
5 0 2 0 2
5 0 0 2 2

样例输出 1

MOVE 1 1
ATTACK 1 2
BUY 3 2
MOVE 1 2
ATTACK 1 3
BUY 1 1
MOVE 1 3
TALK 1 4