#2288. 学霸的迷宫
学霸的迷宫
题目描述
学霸抢走了大家的作业,班长为了帮同学们找回作业,决定去找学霸决斗。但学霸为了不要别人打扰,住在一个城堡里,城堡外面是一个二维的格子迷宫,要进城堡必须得先通过迷宫。因为班长还有事情,磨刀不误砍柴功,他为了节约时间,从线人那里搞到了迷宫的地图,准备提前计算最短的路线。可是他现在就委托你帮他找一条最短的路线。
输入格式
第一行两个整数 ,为迷宫的长宽。
接下来 行,每行 个数,数之间没有间隔,为 0 或 1 中的一个。0 表示这个格子可以通过,1 表示不可以。假设你现在已经在迷宫坐标 的地方,即左上角,迷宫的出口在 。每次移动时只能向上下左右 4 个方向移动到另外一个可以通过的格子里,每次移动算一步。数据保证 , 可以通过。
输出格式
第一行一个数为需要的最少步数 。
第二行 个字符,每个字符 ,分别表示上下左右。如果有多条长度相同的最短路径,选择在此表示方法下字典序最小的一个。
样例
输入#1
3 3
001
100
110
输出#1
4
RDRD
输入#2
3 3
000
000
000
输出#2
4
DDRR
数据范围
有 20% 的数据满足:; 有 50% 的数据满足:; 有 100% 的数据满足:。