【普及】推箱子2

顾名思义，在本题中，有且仅有 2 个箱子，2 个目标点！！！ 本题比较卡内存，大家开数组的时候，尽量只开到 15 就好

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

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

######
#____#
#_.$$#
#_#_@#
#___.#
######

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

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

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

输入格式

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

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

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

输出格式

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

6 6 3 4
######
#____#
#_.$$#
#_#_@#
#___.#
######

DLLLUURURRDDUL

提示

【样例 1 解释】

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

【数据范围】

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

来源

• topoac T1018: 迷宫