{"problem":{"name":"[PA 2018] Gra","description":{"content":"**题目译自 [PA 2018](https://sio2.mimuw.edu.pl/c/pa-2018-1/dashboard/) Runda 5 [Gra](https://sio2.mimuw.edu.pl/c/pa-2018-1/p/gra/)** 现在已经是周末了！你终于可以放松一下，玩你最喜欢的策略游戏了。这个游戏的目标是收集地图上的所有金币并将它们运回基地，规则如下： - 地图由","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9082"},"statements":[{"statement_type":"Markdown","content":"**题目译自 [PA 2018](https://sio2.mimuw.edu.pl/c/pa-2018-1/dashboard/) Runda 5 [Gra](https://sio2.mimuw.edu.pl/c/pa-2018-1/p/gra/)**\n\n现在已经是周末了！你终于可以放松一下，玩你最喜欢的策略游戏了。这个游戏的目标是收集地图上的所有金币并将它们运回基地，规则如下：\n\n- 地图由一个 $n\\times n$ 的网格构成。行从上到下编号为 $0$ 到 $n-1$，列从左到右编号为 $0$ 到 $n-1$。我们用 $(r,c)$ 表示第 $r$ 行第 $c$ 列的单元格。两单元格相邻当且仅当它们共享同一条边。\n- 你的基地位于单元格 $(0,0)$，它位于左上角。你可以在那里招募新的角色，并且你必须把收集到的金币带到那里。剩下的 $n^2-1$ 个格子中初始要么有一定数量的金币，要么有一定数量的石头。\n- 游戏中有两种可以在地图上移动的角色：**农民**可以收集金币，但不可以进入有石头的单元格，**坦克**可以清除石头，并且可以进入任何种类的单元格。\n- 游戏分轮次进行。每轮每个角色可以至多移动一次，移动到与它所在的单元格相邻的单元格中。两个角色不能在同一时间处于同一单元格中。所有移动都是瞬时的（移动花费的时间为零）。\n- 如果在一轮结束时，农民位于有金币的单元格中，他就会拿走 $10$ 枚金币并放到自己的背包里。如果单元格中的金币少于 $10$ 枚，他就会全部拿走。农民的背包容量无限。但农民无法进入石头量不为 $0$ 的单元格中。如果在一轮结束时农民回到了基地，他就会把背包里所有的金币放回基地。\n- 如果在一轮结束时，坦克位于有石头的单元格中，它就会清除单元格中的 $10$ 个石头（如果少于 $10$ 个则清除全部）。\n- 最初基地中有 $200$ 枚金币。每买一种角色——农民或者坦克——都要花费 $100$ 金币（买之前在基地中必须至少有这么多金币），买后角色即时出现。所以新角色可以在同一轮移动。\n\n你的任务是，对于每一个输入给定的地图（也就是对于每个测试点），找到一个操作序列，使得按这个操作序列进行游戏后，所有地图上的金币都被运回了基地（并且可能部分或全部花掉了）。换句话说，结束后的地图上，任何单元格中都没有金币，任何农民的背包里也没有金币。命令如下表所示：\n\n|                   命令                   |                           效果                           |\n| :--------------------------------------: | :------------------------------------------------------: |\n|           $\\texttt{R FARMER}$            |              买一个农民角色，并出生在基地中              |\n|            $\\texttt{R TANK}$             |              买一个坦克角色，并出生在基地中              |\n| $\\texttt{M}\\ \\ r_1\\ \\ c_1\\ \\ r_2\\ \\ c_2$ | 将一个角色从 $(r_1,c_1)$ 移动到相邻的格子 $(r_2,c_2)$ 中 |\n|               $\\texttt{=}$               |                         结束这轮                         |\n|              $\\texttt{===}$              |              结束游戏（即目前的这个测试点）              |\n\n你的程序会使用组织者准备的测试数据进行测试，每组测试数据由一定数量的地图——也就是测试点组成。每组测试数据都有一个限制 $k$（请参考「数据范围及限制」一节）。这是对于每组数据平均轮数的限制。换句话说，如果测试数据中有 $T$ 张地图，你的程序必须在最多 $T\\cdot k$ 轮结束所有游戏。我们定义每个测试点的轮数为使用命令 $\\texttt{=}$ 的次数加 $1$。\n\n错误的命令，超出轮数限制或没有达成目标，均会被判为 Wrong Answer。\n\n## Input\n\n第一行包含两个整数 $T,k$，表示测试点个数和平均轮数限制。除了样例外所有测试数据都有 $T=10$。\n\n对于每组数据，第一行一个正整数 $n$。除了样例外所有测试数据都有 $n=20$。\n\n接下来 $n$ 行，每行 $n$ 个整数。$0$ 表示基地（一定位于左上角）。正数 $a$ 意味着这个单元格有 $a$ 枚金币，负数 $a$ 意味着这个单元格有 $|a|$ 个石头。\n\n地图按如下方式生成：对于每组测试数据，组织者会选择一个常数 $p\\ (0\\le p<1)$，表示单元格中有石头的概率。对于每个除基地以外的单元格，随机选择一个在 $0$ 到 $9$ 范围内的整数 $x$，然后将 $a=2^x$ 赋给这个单元格。在此之后，以 $p$ 的概率给这个值乘以 $-1$。\n\n## Output\n\n对于每组测试点，输出操作序列。一条命令输出一行。最多输出 $2\\ 000\\ 000$ 条命令。\n\n[samples]\n\n## Note\n\n#### 样例 1 解释\n\n对于第一个测试点，我们首先买了一辆坦克，并立即从 $(0,0)$ 移动到 $(1,0)$，这样在两轮中清除掉了所有石头。然后我们将坦克移动到 $(1,1)$，在基地中买一个农民，并将其送到 $(2,0)$ 收集金币。当金币收集完后，我们让农民返回金币并清空背包。我们可以在第一轮就购买一个农民，但他需要一直等到坦克清除石头后才能移动。\n\n第二个测试点展示了一种不是最优但正确的答案。注意农民可以在不收集全部金币的情况下离开这个单元格。招募前两个角色就会花掉所有初始金币（$200$），所以我们只能在农民向基地运回 $100$ 金币后买第三个角色。\n\n第一个测试点中使用了 $7$ 轮，第二个测试点使用了 $13$ 轮。平均是 $10$ 轮，没有超过给定 $k$ 的限制。\n\n------------\n\n#### 数据范围\n\n**本题采用捆绑测试**\n\n共有十个子任务，每个子任务包含 $2$ 到 $5$ 个测试数据。确切的 $p$ 值和 $k$ 值如下表所示：\n\n| $\\text{id}$ |   1    |   2    |   3    |   4   |   5   |   6    |   7    |   8    |   9    |  10   |\n| :---------: | :----: | :----: | :----: | :---: | :---: | :----: | :----: | :----: | :----: | :---: |\n|     $p$     |  $0$   |  $0$   |  $0$   |  $0$  |  $0$  | $0.3$  | $0.4$  | $0.5$  | $0.6$  | $0.7$ |\n|     $k$     | $9000$ | $3500$ | $1500$ | $600$ | $370$ | $1000$ | $1500$ | $3500$ | $1200$ | $750$ |\n\n请注意样例和测试数据在地图大小和测试点个数上稍有不同。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9082","tags":["2018","Special Judge","PA（波兰）"],"sample_group":[["2 12\n3\n0 -8 -512\n-16 -1 -128\n8 -2 -512\n3\n0 64 -1\n64 -1 -1\n1 -1 -1","R TANK\nM 0 0 1 0\n=\n=\nM 1 0 1 1\nR FARMER\nM 0 0 1 0\n=\nM 1 0 2 0\n=\nM 2 0 1 0\n=\nM 1 0 0 0\n=\n===\nR FARMER\nM 0 0 0 1\nR FARMER\nM 0 0 1 0\n=\n=\n=\n=\nM 0 1 0 0\n=\nM 0 0 0 1\n=\n=\nM 1 0 2 0\n=\nM 2 0 1 0\n=\nM 1 0 0 0\n=\nM 0 0 1 0\n=\nR FARMER\nM 1 0 2 0\nM 0 0 1 0\nM 0 1 0 0\n=\n==="]],"created_at":"2026-03-03 11:09:25"}}