j02009. 迷宫回放 未做

$n$ 行 $m$ 列迷宫：S 起点、T 终点、# 墙、. 通道，每步上下左右移动一格。求 $S$ 到 $T$ 的最少步数，并回放一条最短路线：依次用 $U$/$D$/$L$/$R$ 表示每步的方向。走不到只输出 -1。

第一行两个整数 $n$, $m$；接下来 $n$ 行每行一个长度为 $m$ 的字符串。

第一行最少步数；第二行方向串（不可达时整个输出只有 -1 一行）。

• 对于 30% 的数据，$n$, $m$ $\le$ 10（DFS 暴力可过）。
• 对于 60% 的数据，$n$, $m$ $\le$ 100。
• 对于 100% 的数据，1 $\le$ $n$, $m$ $\le$ 800，恰好一个 $S$ 与一个 $T$。