牛牛周末去了游乐园走迷宫。这是一个n*m大小的01迷宫,0表示这个位置可以走,1表示有障碍物不能。
走。现在牛牛在起点(1,1),他想要走到终点(n,m)。并且,如果他能够走到终点的话,他想要知道自己是怎么走到终点的。
如果可以走到终点,因为牛牛比较懒他会先保证走的步数最少,又因为牛牛是个追求完美的人,如果有多
条路径步数一样,他会选择走字典序最小的那条。
数据保证起点和终点都是0
输入描述:
第一行输入两个数n和m,表示n*m的迷宫大小。(2≤n、m≤500)
接下来n行,每行m个字符,字符为0或者1,0表示可以走,1表示不能走。
输出描述:
如果牛牛不能走到终点,请输出"-1",如果可以走到终点,第一行请输出牛牛的最小步数k。
接下来一行,输出一个长度为k的字符串(仅包含'D'、'L'、'R'、'U')表示牛牛的路径。
(D表示向下,L表示向左,R表示向右,U表示向上)