まず、各マスを市松模様に白か黒で塗ることを考えます。マス \((i,j)\) に対し \(i+j\) が偶数なら黒で、奇数なら白で塗ります。このとき、\(1\) 回の移動でコマがあるマスの色は必ず変わります。

これを元に答えが Yes となる必要条件を考えます。

[1] \(N\) が奇数の時

マス \((1,1),(N,N)\) はどちらも黒で塗られています。したがって、途中に通る \(N^2-3\) マスは順に白→黒→白→…→白となる必要がありますが、\(N^2-3\) は偶数なのでそのようなことは起こり得ません。したがって、答えは No になります。

[2] \(N\) が偶数の時

[1] と同じ議論により、途中に通る \(N^2-3\) マスは順に白→黒→白→…→白となる必要があります。もし \(A+B\) が偶数なら黒マスの方が多くなり答えは No になります。

以上より、答えが Yes になる必要条件は

• \(N\) が偶数
• \(A+B\) が奇数

となります。そして、これが必要十分条件となります。

この \(2\) つを満たしている \(N,A,B\) に対し、実際に条件を満たす LRUD 文字列を構成します。

上の問題では \(N\times N\) のグリッドを考えていますが、以下ではより拡張し \(H\times W\) のグリッドで考えます。

この問題を再帰的に解くことを考えます。

まず、\(A > 2\) であるならば最初に RR...RDLL...LD と移動することで \((H,W,A,B) \leftarrow (H-2,W,A-2,B)\) の場合に帰着できます。また、\(H-A+1 > 2\) であるならば最後に RR...RDLL...LD と移動することで \((H,W,A,B) \leftarrow (H-2,W,A,B)\) の場合に帰着できます。これらの操作を繰り返すことで \(H=2\) の場合に帰着することができます。

同様の操作を \(W\) 側に対しても考えることで、この問題を \((H,W)=(2,2)\) の場合まで小さくすることができます。\((H,W)=(2,2)\) の場合 \((A,B)=(1,2),(2,1)\) のいずれかなので、それぞれ場合分けして解くことができます。

以上を適切に実装することでこの問題に正答することができます。計算量はテストケース毎に \(O(N^2)\) です。

以下では再帰的に解くとした部分を先頭・末尾につける文字列をそれぞれ保持しループを用いて実装しています。

実装例(Python3)

for _ in range(int(input())):
    n, a, b = map(int, input().split())
    a, b = a - 1, b - 1
    if n % 2 == 1 or (a + b) % 2 == 0:
        print("No")
        continue
    s1 = []
    s2 = []
    for _ in range(n // 2 - 1):
        s = "R" * (n - 1) + "D" + "L" * (n - 1) + "D"
        if a >= 2:
            s1.append(s)
            a -= 2
        else:
            s2.append(s[::-1])
    for _ in range(n // 2 - 1):
        s = "DRUR"
        if b >= 2:
            s1.append(s)
            b -= 2
        else:
            s2.append(s[::-1])
    assert (a, b) in ((0, 1), (1, 0))
    if (a, b) == (0, 1):
        s1.append("DR")
    else:
        s1.append("RD")
    ans = "".join(s1) + "".join(s2[::-1])
    print("Yes")
    print(ans)