CSES2418 网格路径构建
#CS2418. 网格路径构建
网格路径构建
题目背景
翻译自 CSES-2418 题。
题目描述
给定一个 n×mn \times mn×m 的网格和两个方格 a=(y1,x1)a = (y_1, x_1)a=(y1,x1) 和 b=(y2,x2)b = (y_2, x_2)b=(y2,x2)，从方格 a 到方格 b 构建一条路径，并且路径需要访问每个方格恰好一次。
例如，下面是在一个 4×74 \times 74×7 的网格中，从 a=(1,3)a = (1, 3)a=(1,3) 到 b=(3,6)b = (3, 6)b=(3,6) 的一条路径：
输入格式
第一行包含一个整数 t，表示测试的个数。
接下来有 t 行，每行包含六个整数：n、m、y1y_1y1、x1x_1x1、y2y_2y2 和 x2x_2x2，分别表示网格的行数和列数，起点 a 和终点 b 的位置。
在所有测试中：
-
1≤y1,y2≤n1 \leq y_1, y_2 \leq n1≤y1,y2≤n
-
1≤x1,x2≤m1 \leq x_1, x_2 \leq m1≤x1,x2≤m
-
且 y1≠y2y_1 \neq y_2y1=y2 或 x1≠x2x_1 \neq x_2x1=x2。
输出格式
如果可以构建一条路径，输出 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
RDLURDDRURDRURD
说明/提示