Codeforces Round #504 E. Down or Right

题目描述：交互题。 有一个\(n \times n\)的方阵，有一些格子是障碍，从\((1, 1)\)出发，只能向右向下走，能走到\((n, n)\)，你有\(4n\)次询问，每次询问\((r_1, c_1)\)能否走到\((r_2, c_2)\)，但这两个点的曼哈顿距离要大于\(n-1\)，最后输出一条从\((1, 1)\)到\((n, n)\)的路径。

solution

从\((1, 1)\)出发，优先向下走，向下走能到\((n, n)\)就向下走，走到对角线。然后从\((n, n)\)出发，优先向左走，\((1, 1)\)能到左边的点就向左走，走到对角线，这样构造能保证最终在对角线的点一定重合。

因为优先向下走能保证\(D_1-R_1\)最大，那后面一半的\(R_2-D_2=(n-1-R_1)-(n-1-D_1)=D_1-R_1\)最大，而优先向左走正是保证\(R_2-D_2\)最大，因此对角线的点一定重合。

时间复杂度：\(O(2n)\)

#include <bits/stdc++.h>

using namespace std;

int n;

vector<char> ans;

char st[10];

bool ask(int r1, int c1, int r2, int c2)

{

	printf("? %d %d %d %d\n", r1, c1, r2, c2);

	fflush(stdout);

	scanf("%s", st);

	return st[0]=='Y';

}

void solve()

{

	scanf("%d", &n);

	int x=1, y=1;

	for (int i=1; i<=n-1; ++i)

		if (ask(x+1, y, n, n)) x++, ans.push_back('D');

		else y++, ans.push_back('R');

	x=n, y=n;

	for (int i=1; i<=n-1; ++i)

		if (ask(1, 1, x, y-1)) y--, ans.push_back('R');

		else x--, ans.push_back('D');

	printf("! ");

	for (int i=0; i<n-1; ++i) putchar(ans[i]);

	for (int i=n*2-2-1; i>=n-1; --i) putchar(ans[i]);

	puts("");

	fflush(stdout);

}

int main()

{

	solve();

	return 0;

}