这是一个交互问题。
有一个由 $$$n\times m$$$ 个单元格组成的网格。两个宝箱埋在网格的两个不同单元格中。你的任务是找到他们两个。您可以进行两种类型的操作:
- 挖掘$$$r$$$$$$c$$$:尝试在单元格$$$(r, c)$$$中找到宝藏。互动器会告诉你是否找到了宝藏。
- 扫描$$$r$$$$$$c$$$:从单元格 $$$(r, c)$$$ 开始扫描。此操作的结果是从单元格 $$$(r, c)$$$ 到隐藏宝藏的单元格的曼哈顿距离之和。从单元格 $$$(r_1, c_1)$$$ 到单元格 $$$(r_2, c_2)$$$ 的曼哈顿距离计算为 $$$|r_1 - r_2| + |c_1 - c_2|$$$。
您最多需要7次操作才能找到宝藏。这包括两者 挖掘 和 扫描 操作总数。要解决测试,您需要调用 挖掘 在两个藏有宝藏的牢房中至少操作一次。
互动
您的程序必须在一次运行中处理多个测试用例。首先,测试系统写入 $$$t$$$ — 测试用例的数量 ($$$1\le t \le 100$$$)。然后,$$$t$$$测试用例应该被一一处理。
在每个测试用例中,您的程序应首先读取整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n, m \le 16$$$)。
然后,您的程序可以进行两种类型的查询:
- 挖掘$$$r$$$$$$c$$$ ($$$1\le r\le n$$$; $$$1\le c\le m$$$)。如果你找到了宝藏,交互器会返回整数 $$$1$$$,如果没有找到,则返回 $$$0$$$。如果您多次尝试在同一个单元格中寻找宝藏,结果将为 $$$0$$$,因为宝藏已经被发现。
- 扫描$$$r$$$$$$c$$$ ($$$1\le r\le n$$$; $$$1\le c\le m$$$)。交互器响应一个整数,该整数是从单元 $$$(r, c)$$$ 到隐藏宝藏的单元的曼哈顿距离之和。即使您已经找到其中之一,也会计算两个有宝藏的单元格的总和。
在你找到两个宝藏之后,i。 e.您收到了两人份的 $$$1$$$ 挖掘 操作时,您的程序应继续执行下一个测试用例,或者如果该测试用例是最后一个测试用例则退出。
示例
输入复制
1 2 3 1 1 3 0 1
输出复制
SCAN 1 2 DIG 1 2 SCAN 2 2 DIG 1 1 DIG 1 3