CF1147F Zigzag Game

给定一个包含 $2n$ 个节点的完全二分图，每一侧各有 $n$ 个节点。节点 $1$ 到 $n$ 位于二分图的一侧，节点 $n+1$ 到 $2n$ 位于另一侧。你还会得到一个 $n \times n$ 的矩阵 $a$，描述了边的权值。$a_{ij}$ 表示节点 $i$ 与节点 $j+n$ 之间的边的权值。每条边的权值都不相同。 Alice 和 Bob 在这个图上玩一个游戏。首先，Alice 选择自己要扮演“递增”还是“递减”，Bob 获得剩下的选择。然后，Alice 可以把一个棋子放在图上的任意一个节点。接着，Bob 沿着该节点的任意一条相邻边移动棋子。之后，双方轮流进行如下操作，Alice 先手。 当前玩家必须将棋子从当前顶点移动到某个相邻且未访问过的顶点。设 $w$ 为上一次经过的边的权值。如果玩家扮演的是“递增”，则所经过的边的权值必须严格大于 $w$；如果扮演的是“递减”，则必须严格小于 $w$。无法行动的玩家判负。 给定 $n$ 以及图中各边的权值。你可以选择扮演 Alice 或 Bob，并将与评测机对战。你必须赢得所有对局，答案才会被判为正确。

每组测试数据包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 50$）。每组测试用例描述如下。 每组测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 50$），表示二分图每侧的节点数。 接下来的 $n$ 行，每行包含 $n$ 个整数 $a_{ij}$（$1 \leq a_{ij} \leq n^2$）。$a_{ij}$ 表示节点 $i$ 与节点 $j+n$ 之间的边的权值。所有 $a_{ij}$ 均不相同。 你首先输出一个字符串 "A" 或 "B"，表示你选择扮演 Alice 还是 Bob（"A" 表示 Alice，"B" 表示 Bob）。 如果你扮演 Alice，首先输出 "I" 或 "D"，表示你选择“递增”或“递减”。然后，输出你选择的起始节点编号。 如果你扮演 Bob，先读入一个字符 "I" 或 "D"（表示评测机选择“递增”或“递减”），再读入评测机选择的起始节点编号。 每次移动时，输出你要移动到的节点编号。若要读取评测机的移动，则从标准输入读取一个整数。 如果评测机返回 $-1$，表示评测机已无合法移动（或直接认输），你赢得本局，立即停止处理本组数据，进入下一组。 如果评测机返回 $-2$，表示你进行了非法操作，应立即退出以避免获得其他判定。 如果你无法行动或选择认输，输出 $-1$ 并立即退出，这将导致 Wrong answer 判定。 每次输出移动后，别忘了输出换行并刷新输出缓冲区。否则会因超时被判为 Idleness limit exceeded。具体刷新方法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 Hack 格式 进行 Hack 时，使用如下格式。注意每次只能 Hack 一个测试用例。 第一行包含一个整数 $t$（$t=1$）。 第二行包含一个整数 $n$（$1 \leq n \leq 50$）。 接下来的 $n$ 行，每行包含 $n$ 个整数 $a_{ij}$（$1 \leq a_{ij} \leq n^2$）。$a_{ij}$ 表示节点 $i$ 与节点 $j+n$ 之间的边的权值。所有 $a_{ij}$ 必须互不相同。 评测机会在该用例下随机选择合法移动与你的程序对战。如果评测机无合法移动，则会认输并宣布你获胜。

（见上文输入格式说明）

第一个样例包含两个测试用例。在第一个测试用例中，图如下所示：  在样例输出中，玩家选择扮演 Alice，并选择“递减”，起始于节点 $3$。评测机响应移动到节点 $6$。随后，玩家移动到节点 $2$。此时，评测机已无可走的合法步（因为权值必须“递增”），于是认输并输出 $-1$。 在下一个测试用例中，有两个节点，通过权值为 $1$ 的边相连。玩家选择扮演 Bob。无论评测机如何选择，玩家都可以将棋子移动到另一个节点，评测机无路可走，因此会输掉比赛。 由 ChatGPT 4.1 翻译