这是一个交互问题。
Bob 生活在一个大小为 $$$n \times n$$$ 的方形网格中,行从上到下编号为 $$$1$$$ 到 $$$n$$$,列从左到右编号为 $$$1$$$ 到 $$$n$$$。每个单元格要么被允许,要么被阻止,但您不知道网格的确切描述。您仅获得一个整数 $$$n$$$。
Bob 可以穿过允许的单元格,但只能在某些有限的方向上移动。当 Bob 位于网格中允许的单元格中时,如果允许,他可以向下或向右移动到相邻单元格。
您最多可以提出 $$$4 \cdot n$$$ 形式的查询“? $$$r_1$$$ $$$c_1$$$ $$$r_2$$$ $$$c_2$$$” ($$$1 \le r_1 \le r_2 \le n$$$, $$$1 \le c_1 \le c_2 \le n$$$)。如果 Bob 可以从单元格 $$$(r_1, c_1)$$$ 到达单元格 $$$(r_2, c_2)$$$,则答案为“是”,否则为“否”。特别地,如果两个小区之一(或两者)是阻塞小区,则答案肯定是“否”。由于 Bob 不喜欢短途旅行,因此您只能询问两个单元格之间的曼哈顿距离至少为 $$$n - 1$$$ 的查询,即必须满足以下条件:$$$(r_2 - r_1) + (c_2 - c_1) \gen - 1$$$。
保证 Bob 可以从左上角 $$$(1, 1)$$$ 到达右下角 $$$(n, n)$$$,而你的任务就是找到一种方法来做到这一点。您应该以“!S”的形式打印答案,其中$$$S$$$是长度为$$$2 \cdot n - 2$$$的字符串,由字符“D”和“R”组成,分别表示向下和向右移动。向下移动将第一个坐标增加 $$$1$$$,向右移动将第二个坐标增加 $$$1$$$。如果有多个解决方案,则任何一个都将被接受。打印解决方案后应立即终止。
输入
输入的唯一行包含一个整数 $$$n$$$ ($$$2 \le n \le 500$$$) — 网格的大小。
互动
您最多可以提出 $$$4 \cdot n$$$ 查询。要提出查询,请打印包含“? $$$r_1$$$ $$$c_1$$$ $$$r_2$$$ $$$c_2$$$ 的行($$$1 \le r_1 \le r_2 \le n$$$, $$$1 \le c_1 \le c_2 \le n$$$)。之后,您应该根据查询的答案读取包含“是”或“否”的一行。 “YES”表示 Bob 可以从单元格 $$$(r_1, c_1)$$$ 转到单元格 $$$(r_2, c_2)$$$,“NO”表示相反。
请注意,网格在解决方案开始之前是固定的,并且不取决于您的查询。
打印查询后,不要忘记输出行尾并刷新输出。否则您将得到超出空闲限制或其他负面判决。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
回答“BAD”而不是“YES”或“NO”意味着您进行了无效查询。收到“BAD”后立即退出,您将看到错误的答案判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。
输出
当您准备好打印答案时,打印一行包含“! S”,其中 $$$S$$$ 是长度为 $$$2 \cdot n - 2$$$ 的字符串,由字符“D”和“R”组成,分别表示向下和向右移动。该路径应该是从单元格 $$$(1, 1)$$$ 到单元格 $$$(n, n)$$$ 的有效路径,并且仅通过允许的单元格。
示例
输入 #1
4 YES NO YES YES
输出 #1
? 1 1 4 4 ? 1 2 4 3 ? 4 1 4 4 ? 1 4 4 4 ! RDRRDD
注意
第一个示例如下图所示。
要破解,请使用以下输入格式:
第一行应包含一个整数 $$$n$$$ ($$$2 \le n \le 500$$$) — 网格的大小。
接下来的 $$$n$$$ 行应包含 $$$n$$$ 字符“#”或“.”的字符串,其中“#”表示被阻止的单元格,“.”表示被阻止的单元格。表示允许的单元格。
例如,以下文本对上面显示的示例进行编码: