#645 Magic Path

题面

题面语言

在一个 $N\times M$ 的网格中，每个格子可能有人居住，也可能无人居住。行从上到下编号为 $0,1,\cdots,N-1$ ，列从左到右编号为 $0,1,\cdots,M-1$ 。格点的坐标记为 $(i,j)$ ，其中 $0\le i\le N$ ， $0\le j\le M$ 。

你需要输出一条从 $(0,0)$ 到 $(N,M)$ 、沿网格线移动的路径。每次移动可以到达上、下、左、右相邻的格点，但不能移出网格。

对于每个有人居住的格子，如果路径访问过构成该格子的四个顶点中的至少一个，则会在该格子产生 $1$ 的费用。即使多次访问同一格子的顶点，该格子的费用也只计算一次。路径的费用为产生费用的格子数量。

具体评分方式请参见 Scoring 一节。

输入格式如下。

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

对于每个测试用例，输出以下两行。

$C\ K$ $S$

$S$ 是一个长度为 $K$ 的字符串，其中每个字符均为 U、D、L、R 之一，分别表示从当前格点向上、向下、向左、向右移动一格。

$S$ 所表示的移动必须从开始，始终位于网格内，并最终到达。

本题对每个子任务独立评分，以下近似比标准对所有子任务均相同。

设某个测试用例的最优费用为 $o$ ，选手输出的有效路径的实际费用为 $a$ 。定义近似比 $c$ ：

c = {\begin{cases} \frac{a}{o}, & o > 0, \\ 1, & o = 0 且 a = 0, \\ + \end{cases}

#	分数	限制
1	9	附加条件：每个测试用例均满足 $NM\le 10^4$ 。
2	11	附加条件：每个测试用例均满足 $NM\le 10^5$ 。

样例输入

样例输出

0 2
DR
1 3
DRR
0 6
RRRDDD
3 4
DDRR

在第一个测试用例中，没有任何格子有人居住，因此所输出路径的费用为 $0$ 。

在第二个测试用例中，左侧格子有人居住，而起点 $(0,0)$ 是该格子的一个顶点，因此无论选择哪条路径，费用都至少为 $1$ 。样例路径的费用为 $1$ 。

在第三个测试用例中，虽然存在有人居住的格子，但所输出路径没有访问该格子的任何顶点。因此路径的费用为 $0$ 。