z题目背景

星际探索者酥酥在一次勇敢的探险中，不慎降落在了一个未知的星球上。这个星球表面布满了复杂的地形和未知的障碍，酥酥必须找到一条安全的路线返回她的飞船。

星球的表面可以用一个巨大的矩阵网格来表示，每个网格单元包含了不同的地形信息，这使得酥酥的行进充满了挑战。你能帮助酥酥找到返回飞船的最短路径吗？

题目描述

给定一个 $n$ 行 $m$ 列的 $01$ 矩阵，表示星球表面的地形图，矩阵中的每个单元格 $(i, j)$ 对应于星球表面的一个特定位置（ $1 \leq i \leq n$ ， $1 \leq j \leq m$ ）。

你的任务是帮助酥酥从矩阵的左上角（起点）前往右下角（飞船所在地）。她的移动规则如下：

酥酥当前位于格子 $(i, j)$ 时，她下一步可以移动到 $(i - 1, j)$ 、 $(i + 1, j)$ 、 $(i, j - 1)$ 或 $(i, j + 1)$ 中的任何一个格子。
酥酥不能离开这个矩阵的范围，即她的位置 $(i, j)$ 必须始终满足 $1 \leq i \leq n$ 和 $1 \leq j \leq m$ 。
酥酥移动时，两个格子的地形必须不同。即如果一个格子标记为 $0$ ，她只能移动到标记为 $1$ 的格子上，反之亦然。

酥酥每移动一步将消耗一定的时间。你的目标是找到一条耗时最短的路径，帮助她从 $(1, 1)$ 到达 $(n, m)$ 。除了给出最短耗时外，还需给出一种符合最短耗时的具体移动方案。

本题中每个测试点包含多组测试数据。第一行为一个正整数 $T$ ，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $n, m$ （ $1 \leq n, m \leq 2 \times 10^3$ ），分别表示矩阵的行数和列数。接下来的 $n$ 行，每行包含一个长度为 $m$ 的字符串，仅由字符 0 和 1 组成，表示星球的地形图。

所有测试数据的 $n$ 之和和 $m$ 之和均不超过 $2 \times 10^3$ 。

对每组测试数据，输出一行或两行：

如果酥酥无法从起点到达飞船，仅输出一行 -1 表示无解。

否则，按照以下规则输出：

第一行输出一个整数 $t$ ，表示酥酥从起点到飞船的最短耗时。
第二行输出一个长度为 $t$ $t$ 的字符串 $s$ $s$ ，仅由字符 L、R、U、D 组成，表示酥酥的移动方向：
- 若酥酥的第 $i$ 次移动是从 $(i, j)$ 向上移动到 $(i - 1, j)$ ，则 $s_i = \texttt{U}$ 。
- 若酥酥的第 $i$ 次移动是从 $(i, j)$ 向下移动到 $(i + 1,j)$ , 则 $s_i = \texttt{D}$ 。
- 若酥酥的第 $i$ 次移动是从 $(i, j)$ 向下移动到 $(i ,j-1)$ , 则 $s_i = \texttt{L}$ 。
- 若酥酥的第 $i$ 次移动是从 $(i, j)$ 向下移动到 $(i ,j+1)$ , 则 $s_i = \texttt{R}$ 。

输入 #1

输出 #1

2
RD
-1