P15074 [ICPC 2024 Chengdu R] Chinese Chess

**这是一道交互题。** 中国象棋是一种在中国非常流行的双人策略棋盘游戏。中国象棋棋盘共有 $10$ 行 $9$ 列。我们用 $(r,c)$ 表示从下往上数第 $r$ 行、从左往右数第 $c$ 列的点（$0 \le r \le 9$，$0\le c \le 8$）。 :::align{center}  ::: 本题中涉及六种棋子：将（帅）、士、车、马、象（相）和兵（卒）。注意，炮不考虑在内。此外，所有棋子都可以移动到棋盘上的任何位置，这与原始规则略有不同。每种棋子的移动规则如下（假设当前位置为 $(r, c)$）： $$ \begin{array}{|c|c|c|} \hline \textbf{\text{棋子}} & \textbf{\text{符号}} & \textbf{\text{一次移动可到达的位置}} \\ \hline \text{将（帅）} & J & (r+1, c)\ (r-1, c)\ (r, c+1)\ (r, c-1) \\ \hline \text{士} & S & (r+1, c+1)\ (r+1, c-1)\ (r-1, c+1)\ (r-1, c-1) \\ \hline \text{车} & C & \text{所有满足 }r'=r\text{ 或 }c'=c\text{ 的 }(r', c')\text{，除了 }(r, c)\text{ 本身} \\ \hline \text{马} & M & (r+2, c+1)\ (r+2, c-1)\ (r-2, c+1)\ (r-2, c-1) \\ & & (r+1, c+2)\ (r+1, c-2)\ (r-1, c+2)\ (r-1, c-2) \\ \hline \text{象（相）} & X & (r+2,c+2)\ (r+2,c-2)\ (r-2,c+2)\ (r-2,c-2) \\ \hline \text{兵（卒）} & B & (r+1, c)\text{ 如果 }r \le 4\text{，否则 }(r+1,c)\ (r,c+1)\ (r,c-1) \\ \hline \end{array} $$ 当然，棋子不能移出棋盘边界。现在你已经了解了规则，让我们开始游戏。 我在棋盘上放置了一枚棋子，你看不到它的位置或类型。但是，我会提供一个可能包含棋子位置的集合 $A$，其大小为 $n$。你的目标是使用最少的查询次数来确定棋子的类型。对于每次查询，你可以选择一个棋盘上的位置，我将告诉你棋子移动到该位置所需的最少步数，或者告诉你棋子不可能到达该位置。 这很有趣，不是吗？更有趣的是，我其实在暗中与你对抗。实话实说，尽管集合 $A$ 是固定的，但我并没有从一开始就固定这枚棋子的类型和位置。我的策略是调整对你每次查询的回应，以最大化你的查询次数，同时不与已给出的信息相矛盾。在我们双方都采用最优策略的情况下，你的查询次数 $m$ 实际上是可确定的。我相信你足够聪明，能够将其推算出来。游戏开始！ ### 交互方式 首先，你应该从标准输入读取一个整数 $n$（$1\le n\le 90$），表示集合 $A$ 的大小。 然后，读取 $n$ 行。每行包含两个整数 $r$ 和 $c$，表示集合 $A$ 中的一个位置。保证所有位置互不相同。 读取这 $n+1$ 行后，你应该向标准输出输出一个整数 $m$，表示查询次数。如果你的输出 $m$ 不正确，你将得到 **Wrong answer** 的判定。然后你必须恰好进行 $m$ 次查询。 要进行一次查询，请在一行中输出 `? r c`（$0\le r\le 9, 0\le c\le 8$）。然后你应该从标准输入读取一个整数，表示棋子移动到所选位置所需的最少步数，如果棋子无法移动到该位置，则为 $-1$。如果你的程序进行了无效查询或超过了查询次数，交互器将立即终止，你将收到 **Wrong answer** 的判定。 要输出你对棋子类型的猜测，你需要输出 `! ch`，其中 `ch` 表示题目描述中代表该棋子的符号。 在你进行一次查询或输出你的答案（包括 $m$ 和棋子类型）后，请不要忘记输出换行符 `\n` 并刷新输出缓冲区。为此，请使用： - C++ 中的 `fflush(stdout)` 或 `cout.flush()`； - Java 中的 `System.out.flush()`； - Python 中的 `stdout.flush()`。

无

无

对于第一个示例，六种棋子从位置 $(9, 0)$ 移动到 $(3, 6)$ 所需步数如下： $$ \begin{array}{|c|c|c|c|c|c|} \hline \text{将（帅） (J)} & \text{士 (S)} & \text{车 (C)} & \text{马 (M)} & \text{象（相） (X)} & \text{兵（卒） (B)} \\ \hline 12 & 6 & 2 & 4 & 3 & -1 \\ \hline \end{array} $$ 因此，你只需要进行一次查询即可确定答案。 翻译由 DeepSeek V3 完成