Grid Path Construction

题目描述

给定一个 $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（右）组成的路径描述。如果有多条路径，你可以输出其中任意一条。

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

提示

$1 \le t \le 100$ $1 \le n \le 50$ $1 \le m \le 50$

标签: CSES2418|构造题

来源

CSES2418|构造题