P9082 [PA 2018] Gra

**题目译自 [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\times n$ 的网格构成。行从上到下编号为 $0$ 到 $n-1$，列从左到右编号为 $0$ 到 $n-1$。我们用 $(r,c)$ 表示第 $r$ 行第 $c$ 列的单元格。两单元格相邻当且仅当它们共享同一条边。 - 你的基地位于单元格 $(0,0)$，它位于左上角。你可以在那里招募新的角色，并且你必须把收集到的金币带到那里。剩下的 $n^2-1$ 个格子中初始要么有一定数量的金币，要么有一定数量的石头。 - 游戏中有两种可以在地图上移动的角色：**农民**可以收集金币，但不可以进入有石头的单元格，**坦克**可以清除石头，并且可以进入任何种类的单元格。 - 游戏分轮次进行。每轮每个角色可以至多移动一次，移动到与它所在的单元格相邻的单元格中。两个角色不能在同一时间处于同一单元格中。所有移动都是瞬时的（移动花费的时间为零）。 - 如果在一轮结束时，农民位于有金币的单元格中，他就会拿走 $10$ 枚金币并放到自己的背包里。如果单元格中的金币少于 $10$ 枚，他就会全部拿走。农民的背包容量无限。但农民无法进入石头量不为 $0$ 的单元格中。如果在一轮结束时农民回到了基地，他就会把背包里所有的金币放回基地。 - 如果在一轮结束时，坦克位于有石头的单元格中，它就会清除单元格中的 $10$ 个石头（如果少于 $10$ 个则清除全部）。 - 最初基地中有 $200$ 枚金币。每买一种角色——农民或者坦克——都要花费 $100$ 金币（买之前在基地中必须至少有这么多金币），买后角色即时出现。所以新角色可以在同一轮移动。 你的任务是，对于每一个输入给定的地图（也就是对于每个测试点），找到一个操作序列，使得按这个操作序列进行游戏后，所有地图上的金币都被运回了基地（并且可能部分或全部花掉了）。换句话说，结束后的地图上，任何单元格中都没有金币，任何农民的背包里也没有金币。命令如下表所示： | 命令 | 效果 | | :--------------------------------------: | :------------------------------------------------------: | | $\texttt{R FARMER}$ | 买一个农民角色，并出生在基地中 | | $\texttt{R TANK}$ | 买一个坦克角色，并出生在基地中 | | $\texttt{M}\ \ r_1\ \ c_1\ \ r_2\ \ c_2$ | 将一个角色从 $(r_1,c_1)$ 移动到相邻的格子 $(r_2,c_2)$ 中 | | $\texttt{=}$ | 结束这轮 | | $\texttt{===}$ | 结束游戏（即目前的这个测试点） | 你的程序会使用组织者准备的测试数据进行测试，每组测试数据由一定数量的地图——也就是测试点组成。每组测试数据都有一个限制 $k$（请参考「数据范围及限制」一节）。这是对于每组数据平均轮数的限制。换句话说，如果测试数据中有 $T$ 张地图，你的程序必须在最多 $T\cdot k$ 轮结束所有游戏。我们定义每个测试点的轮数为使用命令 $\texttt{=}$ 的次数加 $1$。 错误的命令，超出轮数限制或没有达成目标，均会被判为 Wrong Answer。

第一行包含两个整数 $T,k$，表示测试点个数和平均轮数限制。除了样例外所有测试数据都有 $T=10$。 对于每组数据，第一行一个正整数 $n$。除了样例外所有测试数据都有 $n=20$。 接下来 $n$ 行，每行 $n$ 个整数。$0$ 表示基地（一定位于左上角）。正数 $a$ 意味着这个单元格有 $a$ 枚金币，负数 $a$ 意味着这个单元格有 $|a|$ 个石头。 地图按如下方式生成：对于每组测试数据，组织者会选择一个常数 $p\ (0\le p

对于每组测试点，输出操作序列。一条命令输出一行。最多输出 $2\ 000\ 000$ 条命令。

#### 样例 1 解释 对于第一个测试点，我们首先买了一辆坦克，并立即从 $(0,0)$ 移动到 $(1,0)$，这样在两轮中清除掉了所有石头。然后我们将坦克移动到 $(1,1)$，在基地中买一个农民，并将其送到 $(2,0)$ 收集金币。当金币收集完后，我们让农民返回金币并清空背包。我们可以在第一轮就购买一个农民，但他需要一直等到坦克清除石头后才能移动。 第二个测试点展示了一种不是最优但正确的答案。注意农民可以在不收集全部金币的情况下离开这个单元格。招募前两个角色就会花掉所有初始金币（$200$），所以我们只能在农民向基地运回 $100$ 金币后买第三个角色。 第一个测试点中使用了 $7$ 轮，第二个测试点使用了 $13$ 轮。平均是 $10$ 轮，没有超过给定 $k$ 的限制。 ------------ #### 数据范围 **本题采用捆绑测试** 共有十个子任务，每个子任务包含 $2$ 到 $5$ 个测试数据。确切的 $p$ 值和 $k$ 值如下表所示： | $\text{id}$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | | :---------: | :----: | :----: | :----: | :---: | :---: | :----: | :----: | :----: | :----: | :---: | | $p$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0.3$ | $0.4$ | $0.5$ | $0.6$ | $0.7$ | | $k$ | $9000$ | $3500$ | $1500$ | $600$ | $370$ | $1000$ | $1500$ | $3500$ | $1200$ | $750$ | 请注意样例和测试数据在地图大小和测试点个数上稍有不同。