P14604 [NWRRC 2025] Eight-Connected Figures

回顾过去三年的题目"K 形图形"、"H 形图形"和"8 形图形"，你可能会好奇今年会是什么类型的几何题。为了给你惊喜，今年评委决定不改变图形的形状，而是改变"形状"本身。今天你需要实时找出"八连通"图形。

**这是一道交互题。** 有一个无限大的正方形网格对你隐藏。每个单元格由一对整数 $(x, y)$ 标识，并且以 $50\%$ 的概率随机染成黑色或白色，各单元格的颜色相互独立。 如果两个单元格共享一条边或一个角，则认为它们是 **相邻的**。因此，每个单元格 $(x, y)$ 有 $8$ 个相邻单元格：$(x-1, y-1)$、$(x-1, y)$、$(x-1, y+1)$、$(x, y-1)$、$(x, y+1)$、$(x+1, y-1)$、$(x+1, y)$ 和 $(x+1, y+1)$。 如果对于集合 $S$ 中的任意两个单元格，存在一条仅使用 $S$ 中单元格的路径连接它们，且路径中连续的单元格是相邻的，则称单元格集合 $S$ 是 **八连通的**。 在一次查询中，你可以了解网格上任意单元格的颜色。你的任务是找到一个包含 $n$ 个单元格的八连通集合，且该集合中的所有单元格颜色相同。 你需要解决 $t$ 个测试用例。在每个测试用例中，网格的染色是随机的，且与其他测试用例相互独立。 **在所有测试用例中**，你最多可以进行 $30,000$ 次查询。

第一行包含两个整数 $t$ 和 $n$，分别表示测试用例的数量和所需的八连通集合的大小（$1 \le t \le 50$；$2 \le n \le 300$）。 ### 交互协议 在每个测试用例中，你可以进行零次或多次查询以了解网格单元格的颜色。 要进行查询，请输出一行： - `?` $x$ $y$ 其中 $(x, y)$ 是请求单元格的坐标（$-10^9 \le x, y \le 10^9$）。之后，读取一行包含一个字母：如果单元格 $(x, y)$ 是黑色则为 `B`，如果是白色则为 `W`。 当你准备好呈现一个包含 $n$ 个同色单元格的八连通集合时，输出一行： - `!` $c$ $x_1$ $y_1$ $x_2$ $y_2$ $\ldots$ $x_n$ $y_n$ 其中 $c$ 是表示集合中单元格颜色的字母（黑色为 `B`，白色为 `W`），而 $(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$ 是集合中的 $n$ 个不同单元格（$-10^9 \le x_i, y_i \le 10^9$）。交互器不会对此行作出任何响应。 输出集合后，继续处理下一个测试用例，或者如果这是最后一个测试用例则终止程序。 **在所有测试用例中**（不包括输出集合的行），你最多可以进行 $30,000$ 次查询。如果你超过此限制，交互器将输出 $0$ 而不是通常的响应，你的程序应立即终止以保证获得错误答案的判定。 交互器不是自适应的：测试中使用的所有随机网格都是预先生成的，并且在所有提交中保持不变。

无

在示例中，为了清晰起见，查询和响应之间用空行分隔。在你的程序与交互器的实际交互中，不会有空行。 你的解决方案将在最多 $60$ 个测试文件上进行评估。 --- 翻译由 DeepSeek V3 完成