Interactive Treasure Hunt

题意翻译

### 题目描述 这是一道交互题。 有一个 $n\times m$ 的网格，其中有两个不同的格子有宝藏。有下列两种操作： - DIG $r$ $c$：在 $(r,c)$ 格子进行挖掘，交互器会告诉你这个格子里是否有宝藏； - SCAN $r$ $c$：扫描 $(r,c)$ 格子，交互器会返回这个格子到两个宝藏所在格子的曼哈顿距离之和。$(r_1,c_1)$ 和 $(r_2,c_2)$ 的曼哈顿距离定义为 $|r_1-r_2|+|c_1-c_2|$。 你需要在 $7$ 次操作以内找到两个操作（包含 DIG 和 SCAN 操作），你需要在每个宝藏的位置都至少使用一次 DIG 操作以解决该组数据。 ### 输入格式 无 ### 输出格式 每个测试点包含多组数据。首先，你需要从交互器读入一个正整数 $t$（$1\le t\le 100$）。接下来依次读入这 $t$ 组数据： 每组数据的第一行为两个正整数 $n$ 和 $m$（$1\le n,m\le 16$）。 接下来，你的程序可以进行两种查询： - DIG $r$ $c$：交互器会返回 $1$ 表示这个格子有宝藏，而返回 $0$ 表示没有。若已经对有宝藏的格子进行过 DIG 操作，再一次进行该操作会返回 $0$； - SCAN $r$ $c$：扫描 $(r,c)$ 格子，交互器会返回这个格子到两个宝藏所在格子的曼哈顿距离之和（包括已经找到的宝藏）。 在找到两个宝藏，即有两个 DIG 操作的返回值是 $1$ 时，你需要立即读入下一组数据或是结束程序如果所有数据已经被读入。

题目描述

This is an interactive problem. There is a grid of $ n\times m $ cells. Two treasure chests are buried in two different cells of the grid. Your task is to find both of them. You can make two types of operations: - DIG $ r $ $ c $ : try to find the treasure in the cell $ (r, c) $ . The interactor will tell you if you found the treasure or not. - SCAN $ r $ $ c $ : scan from the cell $ (r, c) $ . The result of this operation is the sum of Manhattan distances from the cell $ (r, c) $ to the cells where the treasures are hidden. Manhattan distance from a cell $ (r_1, c_1) $ to a cell $ (r_2, c_2) $ is calculated as $ |r_1 - r_2| + |c_1 - c_2| $ . You need to find the treasures in at most 7 operations. This includes both DIG and SCAN operations in total. To solve the test you need to call DIG operation at least once in both of the cells where the treasures are hidden.

输入输出格式

输入格式

输出格式

Your program has to process multiple test cases in a single run. First, the testing system writes $ t $ — the number of test cases ( $ 1\le t \le 100 $ ). Then, $ t $ test cases should be processed one by one. In each test case, your program should start by reading the integers $ n $ and $ m $ ( $ 2 \le n, m \le 16 $ ). Then, your program can make queries of two types: - DIG $ r $ $ c $ ( $ 1\le r\le n $ ; $ 1\le c\le m $ ). The interactor responds with integer $ 1 $ , if you found the treasure, and $ 0 $ if not. If you try to find the treasure in the same cell multiple times, the result will be $ 0 $ since the treasure is already found. - SCAN $ r $ $ c $ ( $ 1\le r\le n $ ; $ 1\le c\le m $ ). The interactor responds with an integer that is the sum of Manhattan distances from the cell $ (r, c) $ to the cells where the treasures were hidden. The sum is calculated for both cells with treasures, even if you already found one of them. After you found both treasures, i. e. you received $ 1 $ for two DIG operations, your program should continue to the next test case or exit if that test case was the last one.

输入输出样例

输入样例 #1

1
2 3

1

1

3

0

1

输出样例 #1

SCAN 1 2

DIG 1 2

SCAN 2 2

DIG 1 1

DIG 1 3