CF1666I.Interactive Treasure Hunt

这是一个交互题。

有一个 $n\times m$ 的网格。在网格的两个不同的格子里埋藏着两个宝箱。你的任务是找到它们。你可以进行两种操作：

• DIG $r$ $c$：尝试在格子 $(r, c)$ 挖掘宝藏。交互器会告知你是否找到了宝藏。
• SCAN $r$ $c$：从格子 $(r, c)$ 进行扫描。该操作的结果是从格子 $(r, c)$ 到两个宝藏所在格子的曼哈顿距离之和。曼哈顿距离定义为从格子 $(r_1, c_1)$ 到格子 $(r_2, c_2)$ 的距离为 $|r_1 - r_2| + |c_1 - c_2|$。

你需要在最多 7 次操作内找到两个宝箱。这 7 次操作包括 DIG 和 SCAN 操作的总和。为了解决本题，你需要在两个宝箱所在的格子各进行至少一次 DIG 操作。

你的程序需要在一次运行中处理多组测试数据。首先，测试系统会输出 $t$，表示测试用例的数量（$1\le t \le 100$）。然后，依次处理 $t$ 个测试用例。

在每个测试用例中，你的程序首先读取两个整数 $n$ 和 $m$（$2 \le n, m \le 16$）。

接下来，你可以进行以下两种类型的查询：

• DIG $r$ $c$（$1\le r\le n$；$1\le c\le m$）。交互器会返回整数 $1$，表示你找到了宝藏，否则返回 $0$。如果你在同一格子多次 DIG，结果会是 $0$，因为宝藏已经被找到。
• SCAN $r$ $c$（$1\le r\le n$；$1\le c\le m$）。交互器会返回一个整数，表示从格子 $(r, c)$ 到两个宝藏所在格子的曼哈顿距离之和。无论你是否已经找到宝藏，都会对两个宝藏所在的格子计算距离之和。

当你找到两个宝藏（即有两次 DIG 操作返回 $1$）后，你的程序应继续处理下一个测试用例，或如果已经是最后一个测试用例则退出。

（本题为交互题，无需输出格式说明。）

由 ChatGPT 4.1 翻译