[yLCPC2024] B. 找机厅

题目背景

扶苏正在出发去打 mai! 但是商场内部实在太复杂了,她在里面迷路了。已经在地铁站迷路过一次的扶苏看着商场的地图实在是不懂怎么走,你能帮帮她吗?

题目描述

给定一个 $n$ 行 $m$ 列的 $01$ 矩阵,记矩阵第 $i$ 行第 $j$ 列的格子是 $(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, 1)$ 无法到达 $(n, m)$,输出一行一个 $-1$ 表示无解。 否则按如下规则输出: - 第一行输出一个整数 $t$,表示从左上角走到右下角的最短用时。 - 第二行输出一个长度为 $t$ 的仅含字符 `L` `R` `U` `D` 的字符串 $s$,表示你给出的行走方法: + 如果给出的行走方法第 $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}$。 你第二行输出的字符串长度必须恰好为第一行给出的最短用时 $t$。如果有多种方案符合要求,你可以输出任意一种。

输入输出样例

输入样例 #1

2
2 2
01
11
2 2
01
10

输出样例 #1

-1
2
RD