題目標題已經描述的很清楚了，明顯是一道交互題，讓你去向系統詢問你猜的對不對，然后系統會給你反饋你那些點是取對了，然后你接著問，最多問10次。

當然這個10次包含明顯的暗示，n,m都是1000，那么2^10剛好1024，暗示你用二分的操作來搞，你怎么樣取構造這條路徑才能達到一個最優，但是即使是想到了怎么去走但是如何去code還是很復雜。

隊友盲猜了一個走的方式

對于每一個左上點到右下點我們都選擇這樣得走的方式，記錄每一個點的后趨與前驅。（對應代碼solve函數）

如這第一次走得，至少也得經過三個點（自己理解），系統會返回你走過的點

我們分別記錄我們走得每一個點裝到一個vector里邊去

然后開始遍歷vector里的相鄰的兩個點，如果兩個點位置相鄰（就是兩個點挨著）就直接走

如果兩個點不相鄰

那么第一個點的后驅如果在第一個點的下邊，我們就選擇走右邊，設右邊這個點的位置為pos1，反之亦然

如果第二個點的前驅在第二個點的左邊，我們就選擇他上邊那個點，設上邊那個點的位置為pos2,反之亦然

對pos1，pos2進行solve

類似就變成了二分的過程

然后基本流程就就是這樣，將確定的點丟到set里邊，如果set里邊的點==n+m-2的時候輸出答案。

#include <bits/stdc++.h>
using namespace std;
#define pii(x,y) make_pair(x,y)
#define pr pair<int,int>
const int maxn=1e3+5;
int a[maxn][maxn];
map<pr,pr> pre,nex;
int n,m;
set<pr>ans;
vector<pr> v;
void solve(int sx,int sy,int ex,int ey)
{if(sx==ex&&sy==ey) return;pr pos=pii(sx,sy);int mid=(sx+ex+1)/2;while(pos.first<mid){cout<<"D";pre[pii(pos.first+1,pos.second)]=pii(pos.first,pos.second);nex[pii(pos.first,pos.second)]=pii(pos.first+1,pos.second);pos.first++;}while(pos.second<ey){cout<<"R";pre[pii(pos.first,pos.second+1)]=pii(pos.first,pos.second);nex[pii(pos.first,pos.second)]=pii(pos.first,pos.second+1);pos.second++;}while(pos.first<ex){cout<<"D";pre[pii(pos.first+1,pos.second)]=pii(pos.first,pos.second);nex[pii(pos.first,pos.second)]=pii(pos.first+1,pos.second);pos.first++;}
}
int main()
{cin>>n>>m;cout<<"? ";solve(1,1,n,m);cout<<endl;int c;cin>>c;int x,y;for(int i=1;i<=c;i++){cin>>x>>y;a[x][y]=1;ans.insert(pii(x,y));v.push_back(pii(x,y));}if(ans.size()==n+m-1){printf("! ");for(int i=1;i<v.size();i++){pr now=v[i],t=v[i-1];if(now.first==t.first+1) cout<<"D";else cout<<"R";}cout<<endl;return 0;}int tim=9;while(tim--){cout<<"? ";int cc=0;pr noww;noww.first=1,noww.second=1;cc++;while(1){if(a[noww.first+1][noww.second]) noww.first++,cc++,cout<<"D";else if(a[noww.first][noww.second+1]) noww.second++,cc++,cout<<"R";else{pr c=nex[noww];if(c.first==noww.first+1){cout<<"R";ans.insert(pii(noww.first,noww.second+1));pr d=v[cc];pr e=pre[d];if(e.first+1==d.first){ans.insert(pii(d.first,d.second-1));solve(noww.first,noww.second+1,d.first,d.second-1);cout<<"R";}else{ans.insert(pii(d.first-1,d.second));solve(noww.first,noww.second+1,d.first-1,d.second);cout<<"D";}noww=v[cc];cc++;}else{cout<<"D";ans.insert(pii(noww.first+1,noww.second));pr d=v[cc];pr e=pre[d];if(e.first+1==d.first){ans.insert(pii(d.first,d.second-1));solve(noww.first+1,noww.second,d.first,d.second-1);cout<<"R";}else{ans.insert(pii(d.first-1,d.second));solve(noww.first+1,noww.second,d.first-1,d.second);cout<<"D";}noww=v[cc];cc++;}}if(noww.first==n&&noww.second==m){cout<<endl;break;}}v.clear();cin>>c;int x,y;for(int i=1;i<=c;i++){cin>>x>>y;a[x][y]=1;ans.insert(pii(x,y));v.push_back(pii(x,y));}if(ans.size()==n+m-1){printf("! ");for(int i=1;i<v.size();i++){pr noww=v[i],pre=v[i-1];if(noww.first==pre.first+1) cout<<"D";else cout<<"R";}cout<<endl;return 0;}}
}/*
6 73
1 1
3 4
6 710
1 1
1 2
2 2
2 3
2 4
3 4
4 4
5 5
6 6
6 712
1 1
1 2
2 2
2 3
2 4
3 4
4 4
4 5
5 5
6 5
6 6
6 7*/

?

總結

以上是生活随笔為你收集整理的gym102443 D.Guess the Path的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。