HKBU ICPC Seminar 7-10

D. 神奇怪兽在哪里

单点时限: 2.0 sec

内存限制: 256 MB

熊猫先生最近在玩一款单机游戏。

在游戏中,会有一张 $n$ 行 $m$ 列的地图(如样例中所示)。用 . 表示空地,用 * 表示怪兽,用 P 表示熊猫先生现在所在的位置。怪兽只有一个,所以由 * 组成的块一定是一个上下左右四连通块。游戏的规则是:熊猫先生要把怪兽「包住」,并且回到现在所在的位置,才能把怪兽消灭掉。

「包住」的含义是:走过的路径可以将怪兽封闭起来。只能在空地上行走。走过的路径可以相交,可以重叠,可以重复走,只要围住就好了。

由于这是一款在命令行下运行的复古单机游戏,熊猫先生只能按上下左右四个键,即他只能向上下左右四个方向移动。你能找到一种消灭怪兽的方法吗?

输入格式

输入包含多个测试文件,每个测试文件是单组测试数据。

第一行两个整数 $n, m$ $(1 \leq n, m \leq 100)$。对于 30% 的数据,满足:$1 \leq n,m \leq 20$。

接下来 $n$ 行,每行一个长度为 $m$ 的字符串,表示地图。

. 表示空地,* 表示怪兽,P 表示熊猫先生现在所在的位置。输入保证熊猫先生不会出现在「怪兽里面」。

输出格式

输出一行,一个字符串,表示要消灭怪兽所要执行的操作序列:

  • 向上走用 U 表示;
  • 向下走用 D 表示;
  • 向左走用 L 表示;
  • 向右走用 R 表示。

输入保证有解。输出任意一解即可。

样例

Input
6 10
..........
...***..P.
..**......
..*****...
.....***..
..........
Output
DDDDLLLLLLULUUUURRRRRRDR

提示

样例给出的答案路径是:

.PPPPPPP..
.P.***.PP.
.P**....P.
.P*****.P.
.PP..***P.
..PPPPPPP.

答案可以有多种情形,围出下面的形式也是可以的:

.PPPPPPP..
.P.***.PP.
.P**PPPPP.
.P*****.P.
.PP..***P.
..PPPPPPP.

注意在这种方案中,走过的路发生了重叠。

你甚至还可以绕多圈,以至于变成了这样:

PPPPPPPPPP
PPP***PPPP
PP**PPPPPP
PP*****PPP
PPPPP***PP
PPPPPPPPPP

只要你的输出序列能让你回到原点,这种情况也是正确的。