A29202.平面迷宫
普及-
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
下图给出了一个迷宫的平面图,其中标记为 1 的为障碍,标记为 0 的为可以通行的地方。
4 6
010000
000100
001001
110000
迷宫的入口为左上角,出口为右下角,在迷宫中,只能从一个位置走到这个它的上、下、左、右四个方向之一。
对于上面的迷宫,从入口开始,可以按 DRRURRDDDR
的顺序通过迷宫一共 10 步。其中 D、U、L、R
分别表示向下、向上、向左、向右走。
定一个迷宫 n 行 m 列,请找出一种通过迷宫的方式,其使用的步数最少,在步数最少的前提下,请找出字典序最小的一个作为答案。(请注意在字典序中 D<L<R<U
)
Problem Credits: Macw07。
输入格式
第一行输入迷宫的行 n 和列 m。
输出格式
请找出一种通过迷宫的方式,其使用的步数最少,在步数最少的前提下,请找出字典序最小的一个作为答案
输入输出样例
输入#1
4 6 010000 000100 001001 110000
输出#1
10 DRRURRDDDR
说明/提示
对于 100% 的数据,保证 1≤n≤30,1≤m≤50。