305396: CF1023E. Down or Right
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Down or Right
题意翻译
## 题面 这是一道神奇的**交互**题QwQ Bob**住**在一个N×N(2≤N≤500)的矩阵中，这个矩阵的一些地方是被阻挡的（剩下的就是畅通的）。你并不知道哪里被阻挡了（别问我为什么，问出题人），你只知道N是多少。 Bob可以从一个不被阻挡的格子，向下↓或者是向右→，走到一个也不被阻挡的格子。 那怎么交互呢：你可以询问两个格子(x1,y1)和(x2,y2)**(1≤x1≤x2≤N, 1≤y1≤y2≤N)**，但要保证这两点之间的曼哈顿距离要超过N-1，dis≥N-1，即(x2-x1)+(y2-y1)≥N-1*。 需要以“? x1 y1 x2 y2”的形式进行询问。 CodeForces会给你回复“YES”或“NO”，分别表示这两个点是否能够相通，即从(x1,y1)是否能够走到(x2,y2)。 然后，你最多可以询问4×N次。如果CodeForces回答了“BAD”表示你进行了无效的询问，会直接Wrong Answer掉。 （当然，如果你问一些废话，比如两个被阻挡的格子，答案一定是NO） 题目保证从左上角一定可以走到右下角，你需要以“！S”的方式输出答案，S为一个只包含“D”和“R”的字符串，表示从左上角走到右下角的方案。（special judge，多解输出一组就行了） ## 输入 第一行：N。 剩下的是回答的YES和NO。 ## 输出 询问和答案，格式见样例或者是上面的大段文字。 ## 提示 ```cpp 在输出后记得换行和flush一下： fflush(stdout) or cout.flush() in C++; System.out.flush() in Java; flush(output) in Pascal; stdout.flush() in Python; 其它语言自己搞。。。 ``` ## 样例 第一个样例是这个亚子的（“#”是被阻挡的格子，“.”是可以去的格子）： ```cpp ..#. #... ###. .... ``` 翻译by haiwenhan题目描述
This is an interactive problem. Bob lives in a square grid of size $ n \times n $ , with rows numbered $ 1 $ through $ n $ from top to bottom, and columns numbered $ 1 $ through $ n $ from left to right. Every cell is either allowed or blocked, but you don't know the exact description of the grid. You are given only an integer $ n $ . Bob can move through allowed cells but only in some limited directions. When Bob is in an allowed cell in the grid, he can move down or right to an adjacent cell, if it is allowed. You can ask at most $ 4 \cdot n $ queries of form "? $ 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 $ ). The answer will be "YES" if Bob can get from a cell $ (r_1, c_1) $ to a cell $ (r_2, c_2) $ , and "NO" otherwise. In particular, if one of the two cells (or both) is a blocked cell then the answer is "NO" for sure. Since Bob doesn't like short trips, you can only ask queries with the manhattan distance between the two cells at least $ n - 1 $ , i.e. the following condition must be satisfied: $ (r_2 - r_1) + (c_2 - c_1) \ge n - 1 $ . It's guaranteed that Bob can get from the top-left corner $ (1, 1) $ to the bottom-right corner $ (n, n) $ and your task is to find a way to do it. You should print the answer in form "! S" where $ S $ is a string of length $ 2 \cdot n - 2 $ consisting of characters 'D' and 'R', denoting moves down and right respectively. The down move increases the first coordinate by $ 1 $ , the right move increases the second coordinate by $ 1 $ . If there are multiple solutions, any of them will be accepted. You should terminate immediately after printing the solution.输入输出格式
输入格式
The only line of the input contains an integer $ n $ ( $ 2 \le n \le 500 $ ) — the size of the grid.
输出格式
When you are ready to print the answer, print a single line containing "! S" where where $ S $ is a string of length $ 2 \cdot n - 2 $ consisting of characters 'D' and 'R', denoting moves down and right respectively. The path should be a valid path going from the cell $ (1, 1) $ to the cell $ (n, n) $ passing only through allowed cells. Interaction You can ask at most $ 4 \cdot n $ queries. To ask a query, print a line containing "? $ 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 $ ). After that you should read a single line containing "YES" or "NO" depending on the answer of the query. "YES" means Bob can go from the cell $ (r_1, c_1) $ to the cell $ (r_2, c_2) $ , "NO" means the opposite. Note that the grid is fixed before the start of your solution and does not depend on your queries. After printing a query do not forget to output end of line and flush the output. Otherwise you will get Idleness limit exceeded or other negative verdict. To do this, use: - fflush(stdout) or cout.flush() in C++; - System.out.flush() in Java; - flush(output) in Pascal; - stdout.flush() in Python; - see documentation for other languages. Answer "BAD" instead of "YES" or "NO" means that you made an invalid query. Exit immediately after receiving "BAD" and you will see Wrong answer verdict. Otherwise you can get an arbitrary verdict because your solution will continue to read from a closed stream.
输入输出样例
输入样例 #1
4
YES
NO
YES
YES
输出样例 #1
? 1 1 4 4
? 1 2 4 3
? 4 1 4 4
? 1 4 4 4
! RDRRDD