G - LRUD Moving 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 575 点

問題文

正整数 N,K が与えられます。

N\times N のマス目があり、上から r 行目、左から c 列目のマスをマス (r,c) と表します。

はじめ、コマがマス (1,1) に置かれています。

あなたは以下の操作をちょうど N^2-1 回行い、最終的にコマをマス (N,N) に移動させます：

  • 現在いるマスから、上下左右に隣接するマスへコマを 1 マス移動させる。

ただし、移動中に N^2 個のすべてのマスをそれぞれちょうど 1 回ずつ訪れなければなりません。 ここで、最初にコマが置かれているマス (1,1) も訪れたマスに含めます。

右へ 1 マス移動する操作の回数がちょうど K 回となるような操作列が存在するか判定し、存在する場合はそのような操作列を 1 つ求めてください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 1\le T\le 5\times 10^3
  • 2\le N\le 10^3
  • 0\le K\le N^2-1
  • 全てのテストケースにおける N^2 の総和は 10^6 以下
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

各テストケースは以下の形式で与えられる。

N K

出力

各テストケースに対する答えを順に改行区切りで出力せよ。

各テストケースについて、条件を満たす操作列が存在しない場合は No を出力せよ。

条件を満たす操作列が存在する場合、以下の形式で操作列を出力せよ。

Yes
S_1S_2\dots S_{N^2-1}

ただし、S_k は k 回目の移動を表し、以下のいずれかとする。

  • 左に 1 マス移動する場合は S_k= L
  • 右に 1 マス移動する場合は S_k= R
  • 上に 1 マス移動する場合は S_k= U
  • 下に 1 マス移動する場合は S_k= D

条件を満たす操作列が複数存在する場合、どれを出力しても正答となる。

入力例 1

3
3 4
2 1
5 10

出力例 1

Yes
RRDLLDRR
No
Yes
RRRRDDDLLLURRULLLDDDRRRR

1 番目のテストケースについて考えます。

マス (1,1) から順にマス (1,2),(1,3),(2,3),(2,2),(2,1),(3,1),(3,2),(3,3) と移動させることで右に 1 マス進む操作を 4 回行いマス (3,3) に到達することができます。

Score : 575 points

Problem Statement

You are given positive integers N and K.

There is an N\times N grid. The cell at the r-th row from the top and the c-th column from the left is denoted as cell (r,c).

Initially, a piece is placed on cell (1,1).

You will perform the following operation exactly N^2-1 times so that the piece ends up in cell (N,N):

  • Move the piece one cell to a cell vertically or horizontally adjacent to the cell it is currently on.

Here, over the course of the movement, each of the N^2 cells must be visited exactly once. Cell (1,1), where the piece is initially placed, is considered visited.

Determine whether there exists a sequence of operations where the piece moves one cell to the right exactly K times, and if it exists, find one such sequence.

You are given T test cases; solve each of them.

Constraints

  • 1\le T\le 5\times 10^3
  • 2\le N\le 10^3
  • 0\le K\le N^2-1
  • 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 K

Output

Output the answers for the test cases in order, separated by newlines.

For each test case, if there is no sequence of operations satisfying the condition, output No.

If there exists a sequence of operations satisfying the condition, output it in the following format:

Yes
S_1S_2\dots S_{N^2-1}

Here, S_k represents the k-th move, and is one of the following:

  • S_k= L if the piece moves one cell to the left
  • S_k= R if the piece moves one cell to the right
  • S_k= U if the piece moves one cell up
  • S_k= D if the piece moves one cell down

If there are multiple sequences of operations satisfying the condition, any of them will be accepted.

Sample Input 1

3
3 4
2 1
5 10

Sample Output 1

Yes
RRDLLDRR
No
Yes
RRRRDDDLLLURRULLLDDDRRRR

Consider the first test case.

By moving from cell (1,1) in order to cells (1,2),(1,3),(2,3),(2,2),(2,1),(3,1),(3,2),(3,3), you can move one cell to the right four times and reach cell (3,3).