【普及】迷宫寻路

下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可以通行的地方。

010000
000100
001001
110000

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

对于上面的迷宫，从入口开始，可以按 DRRURRDDDR 的顺序通过迷宫， 一共 10步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。

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

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

输入格式

输入的第一行包含 $6$ 个正整数 $h, w, sx, sy, ex, ey$ 表示迷宫的高，宽，起点的行数，起点的列数，终点的行数，终点的列数；

接下来 $h$ 行，每行包含一个长度为 $w$ 的只包含 0 和 1 的字符串表示迷宫。

题目保证起点和终点是 0，并且存在起点到终点的路径。

输出格式

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

4 6 0 0 3 5
010000
000100
001001
110000

DRRURRDDDR

提示

【样例 1 解释】

【数据范围】

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

来源

• topoac T1018: 迷宫