P17328 [ICPC 2018 Nanjing R] Kangaroo Puzzle

你的朋友制作了一款名为“袋鼠谜题”的电脑视频游戏，想让你帮他试玩一下。正如游戏名称所示，谜题中困着若干只（至少 $2$ 只）袋鼠，玩家的目标是控制它们聚集在一起。只要谜题中的所有袋鼠都聚到一起，它们就能借助袋鼠的神奇力量逃出谜题。 谜题是一个包含 $n \times m$ 个格子的 $n$ 行 $m$ 列网格。某些格子是墙壁，袋鼠无法进入这些格子。其余格子为空地。袋鼠可以向上、下、左、右四个方向移动。保证一只袋鼠可以从任意一个空格子出发到达任意另一个空格子。同时保证谜题中不存在环——也就是说，袋鼠不可能从一个空格子出发，经过若干不同的空格子，再回到初始格子。 初始时，每个空格子上恰好有一只袋鼠。你可以通过按下键盘上的 $\texttt{U}$、$\texttt{D}$、$\texttt{L}$、$\texttt{R}$ 键来控制袋鼠。所有袋鼠会根据你按下的键同时移动。例如，当你按下 $\texttt{U}$ 键时，一只袋鼠若其上方格子存在且为空地，则会向上移动一格；否则原地不动。你最多可以按键 $50000$ 次。如果在 $50000$ 步之后仍有两只袋鼠位于不同格子，你将输掉游戏。

第一行包含两个整数 $n$ 和 $m$ ($1 \leq n,m \leq 20$)，分别表示谜题的行数和列数。接下来的 $n$ 行，每行是一个长度为 $m$ 的、由 $\texttt{0}$ 和 $\texttt{1}$ 组成的字符串，描述谜题的布局。若第 $i+1$ 行第 $j$ 个字符为 $\texttt{1}$，则表示第 $i$ 行第 $j$ 列的格子为空地；否则（即字符为 $\texttt{0}$），该格子为墙壁，不可进入。

输出一个由 $\texttt{U}$、$\texttt{D}$、$\texttt{L}$、$\texttt{R}$ 组成的字符串，使得按照该字符串的顺序按下按键后，所有袋鼠能够聚集到一起。字符串的长度不应超过 $50000$。存在多种可能的合法答案，输出其中任意一种即可。

翻译由 DeepSeek V4 Pro 完成