题目概述

交互题。有一个 $n\times n$ 的网格图，每个格子是空地或者障碍。每次可以往右或者往下走，你可以询问 $(A,B)\to(C,D)$ 是否存在一条合法路径，但需要满足 $|C-A|+|D-B|\ge n-1$ 。不超过 $4n$ 次找出一条从 $(1,1)\to(n,n)$ 的合法路径。

解题报告

可能是斯波题吧……但是太菜了没想到……

这个 $|C-A|+|D-B|\ge n-1$ 的限制非常的神奇，距离 $n-1$ 在两个地方出现了：1.上面到下面，左边到右边的距离。2. $(1,1)$ 到/对角线的距离以及/对角线到 $(n,n)$ 的距离。

第一个和大于等于没什么关系，但是第二个让我们意识到/对角线把网格分成两半。$(1,1)$ 到右下角一半距离均不小于 $n-1$ ，而左上角一半到 $(n,n)$ 也均不小于 $n-1$ 。

所以我们想到左右分开做，最后让两边在/对角线相遇。

不过次数不能超过 $4n$ ，肯定不能乱找一个合法的相遇位置。

于是……左上角在能走到 $(n,n)$ 的前提下尽量往下走，$(1,1)$ 能走到右下角的前提下尽量往左走……就一定能够走到一起，步数只要 $2n$ 步，非常妙。

示例程序

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=500;

int n,LA,LB;char A[(maxn<<1)+5],B[(maxn<<1)+5];bool vis[maxn+5];

inline bool Ask(int A,int B,int C,int D){
    printf("? %d %d %d %d\n",A,B,C,D);fflush(stdout);
    static char s[5];scanf("%s",s);return strcmp(s,"NO");
}
int main(){
    scanf("%d",&n);int s=1,t=1;
    while (true){
        if (n-s+n-t==n-1) {vis[s]=true;break;}
        if (Ask(s+1,t,n,n)) s++,A[++LA]='D'; else t++,A[++LA]='R';
    }
    s=n;t=n;
    while (true){
        if (s-1+t-1==n-1) break;
        if (Ask(1,1,s,t-1)) t--,B[++LB]='R'; else s--,B[++LB]='D';
    }
    putchar('!');putchar(' ');for (int i=1;i<=LA;i++) putchar(A[i]);for (int i=LB;i;i--) putchar(B[i]);return 0;
}