3056. 上下左右

给出一个迷宫的地图,其中 为障碍, 为可通行的地方。

迷宫的入口为左上角,出口为右下角,在迷宫中,只能从一个位置走到这 个它的上、下、左、右四个方向之一。

分别表示向下、向上、向左、向右走,请记录你的最短行径路径,并输出其中字典序最小的一个。

题目保证一定可以到达。

输入

多组输入

每组第一行两个整数

接下输入的矩阵表示地图

输出

输出最短路径中字典序最小的一个

样例

输入#1

4 6
010000
000100
001001
110000

输出#1

DRRURRDDDR



难度等级: 2
总通过次数: 13
总提交次数: 98