#T2294. 网格路径构造(Grid Path Construction)

网格路径构造(Grid Path Construction)

链接: https://cses.fi/problemset/task/2418

板块: Construction Problems

时限: 1.00 s | 内存: 512 MB

题目描述

给定一个 n×mn \times m 的网格以及两个格子 a=(y1,x1)a=(y_1,x_1) 和 b=(y2,x2)b=(y_2,x_2),请构造一条从 aa 到 bb 的路径,使其恰好经过每个格子一次。

例如,下面是在 4×74 \times 7 网格中从 a=(1,3)a=(1,3) 到 b=(3,6)b=(3,6) 的一条路径。

输入

第一行输入一个整数 tt:测试数据的组数。

之后有 tt 行描述这些测试数据。每行包含六个整数 nn、mm、y1y_1、x1x_1、y2y_2 和 x2x_2。

在所有测试数据中都满足 1≤y1,y2≤n1 \le y_1,y_2 \le n 且 1≤x1,x2≤m1 \le x_1,x_2 \le m。此外,还满足 y1≠y2y_1 \neq y_2 或 x1≠x2x_1 \neq x_2。

输出

如果可以构造出这样的路径,输出 YES,否则输出 NO。

如果存在路径,还要输出它的描述,由字符 U(上)、D(下)、L(左)和 R(右)组成。如果存在多条路径,你可以输出其中任意一条。

数据范围

1≤t≤1001 \le t \le 100 1≤n≤501 \le n \le 50 1≤m≤501 \le m \le 50

样例输入

5
1 3 1 1 1 3
1 3 1 2 1 3
2 2 1 1 2 2
2 2 1 1 2 1
4 7 1 3 3 6

样例输出

YES
RR
NO
NO
YES
RDL
YES
RRRRDDDLLLLLLUUURDDRURDRURD