【普及】推箱子1

在本题中，只有一个箱子，一个目标点！！！

相信大家都玩过推箱子游戏，下图是一个推箱子的地图，其中：

• #：代表墙壁，不能通行
• _：代表空地，可以通行
• @：代表玩家
• $：代表箱子
• .：代表箱子的目标地点

######
#___.#
#__#_#
#__$_#
#___@#
######

对于上面的推箱子游戏，可以按 LLURDRUU 的完成游戏， 一共 8 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。

给定任意地图，请找出一种通过游戏的方法，其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。

请注意在字典序中 $D < L < R < U$

输入格式

输入的第一行包含 $4$ 个正整数 $h, w, px, py$ 表示地图的高，宽，玩家的行数，玩家的列数（箱子和目标点的坐标，请自行判断）；

接下来 $h$ 行，每行包含一个长度为 $w$ 的只包含 #，_，@，$，. 的字符串表示地图。

题目保证 只有一个箱子，一个目标点，且存在解决方案

输出格式

输出字典序最小的最短路径

6 6 4 4
######
#___.#
#__#_#
#__$_#
#___@#
######

LLURDRUU

提示

【样例 1 解释】

• 蓝色代表玩家，红色代表箱子，黄色代表目标点
• LLURDRUU

【数据范围】

• 对于 $100\%$ 的数据：$1 \le h, w \le 15$

来源

• topoac T1018: 迷宫