題意
這是一個互動題 有n×m的矩陣，里面有兩個寶藏，你可以進行兩種操作:
第一個是SCAN(x,y),回傳兩個寶藏到點（x，y）的曼哈頓距離(|x-x|+|y-y|)
第二個是DIG(x,y)，如果有坐標有寶藏，回傳1，否則回傳0，當回傳兩個1時，成功找到兩個寶藏
你最多可以操作7次
吐槽
這個題是一次多的機會也不給，七次都是要跑滿的，但是感覺這個題也是挺套路的，絕對值一般都是找兩個鍛煉就可以去掉了，然后分析就很簡單了，
提示
1. 首先需要詢問四個端點中的相鄰兩個，然后就可以推出另外兩個端點的值
2. 當行，或者列固定時，沿著一個方向移動，曼哈頓距離的變化趨勢一定如下：
3. 因此我們只需要詢問上圖平面的中點即可，解方程就可以解出x1,x2
4 .同理，對于y坐標，也需要詢問一次，即可得到y1,y2，那么現在的總次數為 4
5. 由于不知道x，y兩兩如何對應，因此，需要DIG測驗一次，因此最多需要DIG三次，最少DIG兩次，總數6-7次
代碼
#include<bits/stdc++.h>
using namespace std;
int n, m;
int f[10];
int X1, Y1, X2, Y2;//X1<X2,Y1<Y2
void run() {
cin >> n >> m;
cout << "SCAN " << 1 << ' ' << 1 << endl;
cin >> f[1];
cout << "SCAN " << 1 << ' ' << m << endl;
cin >> f[2];
f[3] = (f[1] + f[2] - 2 * m + 6) / 2;//a+c
f[4] = (f[1] - f[2] + 2 + 2 * m) / 2;//b+d
f[5] = 2 * n - f[3] + f[4] - 2;
int res = (f[2] - f[1]) / 2;
int mid = (m - res + 1) / 2;
cout << "SCAN " << 1 << ' ' << mid << endl;
cin >> f[6];//中點
Y1 = (f[1] - f[6]) / 2 + 1;
Y2 = f[4] - Y1;
res = (f[5] - f[1]) / 2;
mid = (n - res + 1) / 2;
cout << "SCAN " << mid << ' ' << 1 << endl;
cin >> f[7];//中點
X1 = (f[1] - f[7]) / 2 + 1;
X2 = f[3] - X1;
cout << "DIG " << X1 << ' ' << Y1 << endl;
cin>>res;
if(res){
cout << "DIG " << X2 << ' ' << Y2 << endl;
cin>>res;
}
else{
cout << "DIG " << X1 << ' ' << Y2 << endl;
cin>>res;
cout << "DIG " << X2 << ' ' << Y1 << endl;
cin>>res;
}
}
int main() {
int t;
cin >> t;
while (t--)
run();
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/525942.html
標籤：其他
上一篇：全球名校AI課程庫（33）| MIT麻省理工 · 計算思維導論(Julia)課程『Introduction to Computational Thinking』