题目

传送门

思路

首先我们考虑限制\(n-1\le(r_i-r_j)+(c_i-c_j)\)具体到图像上表示什么

画个图就能明白，就是从将一个正方形沿对角线切开，每一次询问要从一个顶点询问另一个块中的某一个点

之后我们考虑策略

从\((1,1)\)开始走，在保证走到的那一个点能到达终点的情况下尽可能向右走，不行在向下走

一直走到对角线

之后从\((n,n)\)开始走，能往上走就往上走，不能就往左，一直到对角线

用反证法可以证明这两条路径一定相遇

代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n;
int x,y;
string s1;
string s2;
bool ask(int a,int b,int c,int d)
{
    cout<<'?'<<' '<<a<<' '<<b<<' '<<c<<' '<<d<<endl;
    fflush(stdout);
    string s;
    cin>>s;
    if(s=="YES")
        return 1;
    return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    x=1;
    y=1;
    for(int i=1;i<=2*n;i++)
    {
        if(x+y==n+1)
            break;
        bool t=ask(x,y+1,n,n);
        if(t)   
        {
            s1+='R';
            y++;
        }
        else
        {
            s1+='D';
            x++;
        }
    }
    x=n;
    y=n;
    for(int i=1;i<=2*n;i++)
    {
        if(x+y==n+1)
            break;
        bool t=ask(1,1,x-1,y);
        if(t)
        {
            x--;
            s2+='D';
        }
        else
        {
            y--;
            s2+='R';
        }
    }
    reverse(s2.begin(),s2.end());
    cout<<"! "<<s1+s2;
    return 0;
}

习题：Down or Right

原文：https://www.cnblogs.com/loney-s/p/12260863.html