提示: 欢迎访问OurACM平台。
Problem 2097 Runaway

Accept: 14    Submit: 35
Time Limit: 2000 mSec    Memory Limit : 32768 KB

Problem Description

Runaway是hacker.org上的一款有趣的小游戏。其连接为:http://www.hacker.org/runaway/

在该游戏中,玩家必须给机器人设计一条安全的逃跑路线。游戏开始时,将给出一张N*M的地图,描述了机器人所在的地形。一开始时机器人在左上角(坐标为(0,0))的位置。地图中存在着一些障碍物,用’X’表示。空地用’.’表示。你只能对机器人下达两种指令:

1)‘D’:令机器人向下走一步。即机器人的坐标从(r,c)走到(r+1,c)

2)‘R’:令机器人向右走一步,即机器人的坐标从(r,c)走到(r,c+1)

当机器人的坐标为(N,i),(0<=i<=M)或者(i,M),(0<=i<=N)时,机器人达到安全区域。玩家通过该关卡。

每一关卡中,玩家给出的命令个数必须在[MN,MX]范围内。游戏开始后,机器人将不停地按照玩家给出的命令按顺序移动,直到机器人不能移动【机器人不能进入有障碍物的格子中】或者到达安全格子【坐标为(N,i),(0<=i<=M)或者(i,M),(0<=i<=N)】。

例如玩家给出命令为:DR.机器人将按照DRDRDRDRDRDRDR….一直移动下去。

现在,告诉你初始的关卡信息,请设计一个程序,输出可行方案。由于ghnjk比较懒,不想写SPJ程序,所以,输出的方案必须使得命令个数尽量少,如果依旧存在多种解则请输出字典序最小的一种。

Input

输入为标准输入,输入数据中大约有300组测试数据,每组测试数据格式如下:

第一行包含4个整数N,M,MN,MX分别用空格隔开.其中1<N<=200; 1<M<=200; 1<MN<MX<=N+M

接下来N行,每行M个字符表示N*M的地图信息,其中’X’表示障碍物,’.’表示空白地。数据保证(0,0)点为’.’,且每组数据都有解。

Output

对于每组数据,请输出一行,为一种合法的方案。输出的方案必须使得命令个数尽量少,如果依旧存在多种解则请输出字典序最小的一种。

Sample Input

3 3 2 3 ... ... ... 3 3 2 3 ... ... X.. 3 3 1 3 ... ... X.. 11 11 4 6 ......XX... ..X...XX..X ........X.X ........... .......XX.. ...X.....X. .XX......X. X....X...X. .........X. .X...XX.... ...X.......

Sample Output

DD DR R DDRR

Source

FOJ有奖月赛-2012年11月

Submit  Back  Status  Discuss