P12822 [NERC 2021] Interactive Treasure Hunt

**这是一道交互题。** 有一个 $n \times m$ 的网格。两个宝箱被埋藏在网格的两个不同单元格中。你的任务是找到这两个宝箱。你可以进行两种操作： 1. **DIG** $r$ $c$：尝试在单元格 $(r, c)$ 挖掘宝藏。交互器会告诉你是否找到了宝藏。 2. **SCAN** $r$ $c$：从单元格 $(r, c)$ 进行扫描。该操作的结果是从 $(r, c)$ 到两个宝藏所在单元格的曼哈顿距离之和。曼哈顿距离的计算公式为 $|r_1 - r_2| + |c_1 - c_2|$。 你需要在最多 7 次操作内找到两个宝藏（包括 **DIG** 和 **SCAN** 操作）。为了通过测试，你必须在两个藏有宝藏的单元格中各调用至少一次 **DIG** 操作。 ### 交互协议 你的程序需要在一轮运行中处理多个测试用例。首先，测试系统会给出 $t$ —— 测试用例的数量（$1 \le t \le 100$）。然后，依次处理 $t$ 个测试用例。 在每个测试用例中，你的程序首先需要读取两个整数 $n$ 和 $m$（$2 \le n, m \le 16$）。 然后，你的程序可以发起以下两种查询： 1. **DIG** $r$ $c$（$1 \le r \le n$；$1 \le c \le m$）。交互器会返回整数 $1$（如果找到了宝藏）或 $0$（如果未找到）。如果你多次在同一个单元格挖掘，由于宝藏已被取走，结果将始终为 $0$。 2. **SCAN** $r$ $c$（$1 \le r \le n$；$1 \le c \le m$）。交互器会返回一个整数，表示从 $(r, c)$ 到两个宝藏所在单元格的曼哈顿距离之和。即使你已经找到一个宝藏，该操作仍然会计算两个宝藏的距离之和。 当你找到两个宝藏（即通过 **DIG** 操作两次获得 $1$ 的响应）后，你的程序应继续处理下一个测试用例，或者如果是最后一个测试用例则退出。

参见交互协议。

参见交互协议。

翻译由 DeepSeek V3 完成