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
只要你的输出序列能让你回到原点，这种情况也是正确的。
通知
比赛状态发生变化，点 OK 刷新。
通知