CF1991I.Grid Game

这是一个交互题。

你有一个 $n$ 行 $m$ 列的网格。你需要用 $1$ 到 $n \cdot m$ 的不重复整数填满每个格子。

填好网格后，你将与交互器在这个网格上进行一场游戏。双方轮流选择一个尚未被选中的格子，交互器先手。

在第一回合，交互器可以选择网格中的任意一个格子。之后，每次选择的格子必须与之前已被选中的某个格子正交相邻。如果两个格子有公共边，则称它们正交相邻。游戏持续到所有格子都被选中为止。

你的目标是让你所选格子中的数字之和严格小于交互器所选格子中的数字之和。

每个测试包含多组数据。第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。接下来每组测试用例包含一行两个整数 $n$ 和 $m$（$4 \le n, m \le 10$），分别表示网格的行数和列数。

首先输出 $n$ 行，每行 $m$ 个整数，表示你填入网格的数字。每个整数 $1$ 到 $n \cdot m$ 恰好出现一次。

然后，游戏开始。交互器和你轮流输出坐标，依次选择格子，共进行 $n \times m$ 轮，交互器先手。

每次轮到某一方（无论是你还是交互器），该方都要输出两个整数 $i$ 和 $j$（$1 \le i \le n$，$1 \le j \le m$），表示选择了第 $i$ 行第 $j$ 列的格子。该格子不能在之前被选中过。此外，若不是第一回合，所选格子必须与之前已选的某个格子正交相邻。

如果你的任何输出不合法，评测机会输出 “-1”，你将收到 Wrong Answer 判定。

在所有 $n \cdot m$ 轮结束后，如果你所选格子的数字之和没有严格小于交互器所选格子的数字之和，评测机会输出 “-1”，你将收到 Wrong Answer 判定。

如果你的程序收到 Wrong Answer 判定，必须立即终止。否则，你可能会因为读取已关闭的流而收到任意判定。

输出后不要忘记换行并刷新输出缓冲区，否则会收到 Idleness limit exceeded 判定。具体做法如下：

• C++：使用 fflush(stdout) 或 cout.flush()；
• Java：使用 System.out.flush()；
• Pascal：使用 flush(output)；
• Python：使用 stdout.flush()；
• 其它语言请查阅相关文档。

本题不支持 Hack。

注意，这只是一个示例游戏，不一定代表双方的最优策略。

首先，我们用 $1$ 到 $16$ 的不重复整数如下填充一个 $4 \times 4$ 的网格：

$2$ $3$ $4$ $10$
$12$ $6$ $11$ $15$
$5$ $13$ $16$ $8$
$9$ $7$ $1$ $14$

接下来，游戏开始。

1. 交互器首先选择 $(3, 4)$，即数字 $8$。此时可以选择任意格子。从下一步开始，每次选择的格子都必须与已选格子相邻。
2. 我们选择 $(2, 4)$，即数字 $15$，与 $(3, 4)$ 相邻。
3. 交互器选择 $(4, 4)$，即数字 $14$，与 $(3, 4)$ 相邻。
4. 我们选择 $(4, 3)$，即数字 $1$，与 $(4, 4)$ 相邻。
5. $\ldots$
6. 依此类推，直到所有数字都被选中。

最终，我们选择的数字为 $[15, 1, 16, 5, 4, 2, 11, 13]$，交互器选择的数字为 $[8, 14, 7, 9, 10, 3, 6, 12]$。我们所选数字之和为 $67$，小于交互器所选数字之和 $69$，因此我们赢得了这场游戏。

由 ChatGPT 4.1 翻译