← 返回题目列表

AtCoder · abc454_e

H. LRUD 移动

中文机器翻译题面 查看原题

分数: 450 点

问题陈述

给你正整数 N,A,B。可以保证两者 A 和 B 之间 1 和 N,包括在内。

有一个 N\times N 网格。牢房位于 i从顶部开始的第行和 j从左边算起的第列表示为单元格 (i,j)。最初,将一块放置在单元格中 (1,1).

通过重复 N^2-2 移动,每次将棋子移动到相邻的单元格(上、下、左或右),您想要将棋子移动到单元格 (N,N) 访问除单元格之外的每个单元格时 (A,B)。您不得多次访问同一个单元格(您不得访问单元格 (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).

  • S_k= L 如果棋子从单元格中移动 (i,j) 到单元格 (i,j-1)
  • S_k= R 如果棋子从单元格中移动 (i,j) 到单元格 (i,j+1)
  • S_k= U 如果棋子从单元格中移动 (i,j) 到单元格 (i-1,j)
  • S_k= D 如果棋子从单元格中移动 (i,j) 到单元格 (i+1,j)

如果多个移动序列满足条件,则其中任何一个都将被接受。


示例输入 1

3
2 1 2
3 2 2
4 3 2

示例输出 1

Yes
DR
No
Yes
RRRDLLLDDRRURD

考虑第一个测试用例。

从单元格中的片段开始 (1,1),将其移动两次,如下所示:

  • 将棋子向下移动。该块移动到单元格 (2,1).
  • 将棋子向右移动。该块移动到单元格 (2,2).

此动作序列满足条件。