CF2163E Plegma

本题为双次交互（通信）问题。 有两位参赛者：A 选手和 B 选手。裁判会首先与 A 选手交互。A 选手完成后，裁判会与 B 选手交互。需要注意的是，A 选手和 B 选手不能直接传递信息；他们只能与裁判进行信息的发送与接收，但他们可以预先约定一种用于通信的策略。 裁判手中有一个 $n \times n$ 的二值网格 $G$（该网格的每个单元格取值为 $0$ 或 $1$）。第 $1$ 行是最顶端的行，第 $1$ 列是最左侧的列。网格的连通性定义如下：若存在一条仅经过值为 $1$ 的单元格、每步只能上下左右相邻移动（不允许斜向） 的路径，可以连通任意一对 $G_{i_1,j_1}=1$ 与 $G_{i_2,j_2}=1$ 的单元格，则其连通性为 $1$，否则连通性为 $0$。保证每个网格至少有一个值为 $1$ 的单元格。 首先，裁判与 A 选手交互。裁判会将网格 $G$ 交给 A 选手。A 选手查看网格后需确定两个整数 $r$ 和 $c$ 并发送给裁判。 在 B 选手的交互开始时，B 选手会从裁判处收到第 $r$ 行和第 $c$ 列的所有单元格的值。注意 B 选手不会被告知 $r$ 和 $c$ 的具体数值。 A 选手希望确保 B 选手能够判断出 $G$ 的连通性。你的任务是同时作为 A 选手和 B 选手，设计一种策略，使得 B 选手能够准确判断网格的连通性。请注意，交互过程是非自适应的——即第一次交互得到的网格，与用于判断连通性时（第二次交互）的网格是相同的。

你的代码将在每个测试上运行两次。第一次为 A 选手，第二次为 B 选手。 **第一次运行输入** 第一行输入字符串 first，用于指示本次为第一次运行，你应以 A 选手身份行动。 每个测试点包含多个测试用例。第一行包含整数 $t$（$1 \leq t \leq 10^4$），表示测试用例数。每个测试用例的描述如下。 每个测试用例的第一行包含两个整数 $n$ 和 $C$（$2 \leq n \leq 1000, 0 \leq C \leq 1$）——网格的大小与连通性。 接下来 $n$ 行，每行给出一个长度为 $n$ 的二进制字符串 $G_i$，表示网格的第 $i$ 行。 保证以下条件： - 所有测试用例中 $n^2$ 的总和不超过 $2\cdot 10^6$； - $C$ 与网格信息匹配，即 $C=1$ 表示网格连通，$C=0$ 表示网格不连通； - 每个网格至少有一个值为 $1$ 的单元格。 **第二次运行输入** 第一行输入字符串 second，用于指示本次为第二次运行，你应以 B 选手身份行动。 每个测试点包含多个测试用例。第一行包含整数 $t$（$1 \leq t \leq 10^4$），该值与第一次运行输入中的 $t$ 相等。 每个测试用例的第一行包含一个整数 $n$，为对应网格的大小。 第二行包含一个长度为 $n$ 的二进制字符串 $G_{r, 1}G_{r, 2}\ldots G_{r, n}$，为所选定的第 $r$ 行的内容。整数 $r$ 由第一次交互中 A 选手最终决定，并由裁判传递。 第三行同样为长度为 $n$ 的二进制字符串 $G_{1, c}G_{2, c}\ldots G_{n, c}$，为所选定的第 $c$ 列的内容。整数 $c$ 由第一次交互中 A 选手最终决定，并由裁判传递。 **Hack 格式** 发起 Hack 时，使用如下格式： 第一行输入一个整数 $t$ ($1 \leq t \leq 10^4$)，表示网格数。之后，输入 $t$ 个数据块。 每个数据块的第一行输入一个整数 $n$ ($2 \leq n \leq 1000$)，表示网格大小。 接下来 $n$ 行，每行输入长度为 $n$ 的二进制字符串，分别表示网格的每一行。 保证每个网格至少有一个值为 $1$ 的单元格，且所有测试用例中 $n^2$ 的总和不超过 $2\cdot 10^6$。 注意每个网格的连通性由裁判自行判断，无需在 Hack 输出中写出结果。

**第一次运行（A 选手）**：对于每个测试用例，输出两个整数 $r$ 和 $c$（$1 \leq r,c \leq n$）。表示你希望第二次运行时获得第 $r$ 行和第 $c$ 列的信息。 **第二次运行（B 选手）**：对于每个测试用例，输出一个整数 $C$（$0 \leq C \leq 1$），表示该网格的连通性。

第一个输入样例中的第一个网格如下： 1110 第一次运行时，已知 $n=2$。检查样例后，可以判断连通性为 $1$。 假设 A 选手与 B 选手约定了某种策略，即若连通性为 $1$，则 A 选手应选择末尾为 $0$ 的行和列。例如，第 2 行和第 2 列满足该策略。需要注意，这只是便于演示的示例策略，并非在所有情况都适用。 然后观察第二次运行。此时我们是 B 选手。输入 $n=2$，所选行内容为 $r=[1,0]$，所选列内容为 $c=[1,0]$。由于每行最后一项均为 $0$，B 选手用预先约定的策略判断可知连通性为 $1$。 由 ChatGPT 5 翻译