牛牛走迷宫
题号:NC205060
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

牛牛周末去了游乐园走迷宫。这是一个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表示向上)
示例1

输入

复制
2 2
01
00

输出

复制
2
DR

说明

先向下走,再向右走