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

板块: Construction Problems

时限: 1.00 s ｜ 内存: 512 MB

题目描述

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

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

输入

第一行输入一个整数 $t$：测试数据的组数。

之后有 $t$ 行描述这些测试数据。每行包含六个整数 $n$、$m$、$y_1$、$x_1$、$y_2$ 和 $x_2$。

在所有测试数据中都满足 $1 \le y_1,y_2 \le n$ 且 $1 \le x_1,x_2 \le m$。此外，还满足 $y_1 \neq y_2$ 或 $x_1 \neq x_2$。

输出

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

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

数据范围

$1 \le t \le 100$ $1 \le n \le 50$ $1 \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