/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 450 点
問題文
正整数 N,A,B が与えられます。A,B の値はどちらも 1 以上 N 以下であることが保証されます。
N\times N のグリッドがあります。上から i 行目、左から j 列目のマスをマス (i,j) と表記します。はじめ、コマがマス (1,1) に置かれています。
このコマを上下左右に隣接するマスに動かす移動を N^2-2 回繰り返すことで、マス (A,B) 以外の全てのマスを経由しつつマス (N,N) までコマを動かしたいです。ただし、同じマスを 2 回以上経由してはいけません（マス (1,1),(N,N) も途中で経由してはいけません）。
そのような移動が可能か判定し、可能である場合は移動列を一つ出力してください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1\le T \le 5000
- 2\le N\le 10^3
- 1\le A,B\le N
- (A,B)\neq (1,1),(N,N)
- 全てのテストケースにおける N^2 の総和は 10^6 以下
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
各テストケースは以下の形式で与えられる。
N A B
出力
各テストケースに対する答えを順に改行区切りで出力せよ。
各テストケースについて、条件を満たす移動が不可能である場合 No を出力せよ。
可能である場合、以下の形式で出力せよ。
Yes
S_1S_2\ldots S_{N^2-2}
ただし、S_k は k 回目の移動前のコマの座標をマス (i,j) として、k 回目の移動で
- マス (i,j) からマス (i,j-1) に移動する場合は S_k=
L - マス (i,j) からマス (i,j+1) に移動する場合は S_k=
R - マス (i,j) からマス (i-1,j) に移動する場合は S_k=
U - マス (i,j) からマス (i+1,j) に移動する場合は S_k=
D
と定義する。
条件を満たす移動が複数存在する場合、どれを出力しても正答となる。
入力例 1
3 2 1 2 3 2 2 4 3 2
出力例 1
Yes DR No Yes RRRDLLLDDRRURD
1 番目のテストケースについて考えます。
はじめ、コマがマス (1,1) にある状態から以下のように 2 回移動させます。
- コマを下に移動させる。コマはマス (2,1) に移動する。
- コマを右に移動させる。コマはマス (2,2) に移動する。
この移動は条件を満たしています。
Score : 450 points
Problem Statement
You are given positive integers N,A,B. It is guaranteed that both A and B are between 1 and N, inclusive.
There is an N\times N grid. The cell at the i-th row from the top and j-th column from the left is denoted as cell (i,j). Initially, a piece is placed at cell (1,1).
By repeating N^2-2 moves, each of which moves the piece to an adjacent cell (up, down, left, or right), you want to move the piece to cell (N,N) while visiting every cell except cell (A,B). You must not visit the same cell more than once (you must not visit cells (1,1) and (N,N) in the middle, either).
Determine whether such a sequence of moves is possible, and if so, output one such sequence.
You are given T test cases; solve each of them.
Constraints
- 1\le T \le 5000
- 2\le N\le 10^3
- 1\le A,B\le N
- (A,B)\neq (1,1),(N,N)
- The sum of N^2 over all test cases is at most 10^6.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
N A B
Output
Output the answers for the test cases in order, separated by newlines.
For each test case, if it is impossible to perform a sequence of moves satisfying the conditions, output No.
If it is possible, output in the following format:
Yes
S_1S_2\ldots S_{N^2-2}
Here, S_k is defined as follows, where the coordinates of the piece before the k-th move is cell (i,j).
- S_k=
Lif the piece moves from cell (i,j) to cell (i,j-1) - S_k=
Rif the piece moves from cell (i,j) to cell (i,j+1) - S_k=
Uif the piece moves from cell (i,j) to cell (i-1,j) - S_k=
Dif the piece moves from cell (i,j) to cell (i+1,j)
If multiple sequences of moves satisfy the conditions, any of them will be accepted.
Sample Input 1
3 2 1 2 3 2 2 4 3 2
Sample Output 1
Yes DR No Yes RRRDLLLDDRRURD
Consider the first test case.
Starting with the piece at cell (1,1), move it twice as follows:
- Move the piece downward. The piece moves to cell (2,1).
- Move the piece rightward. The piece moves to cell (2,2).
This sequence of moves satisfies the conditions.