#include<bits/stdc++.h>
using namespace std;
struct node{//结构体表示坐标
int x;
int y;
};
char mp[31][51]; //存地图
char k[4]={'D','L','R','U'};//存方向
int dir[4][2]={{1,0},{0,-1},{0,1},{-1,0}};
int vis[30][50]; //1:已经搜过,不用再搜
char pre[31][51]; //用于查找前驱点。例如pre[x][y] = ‘D’,表示上一个点往下走一步到了(x,y),那么上一个点是(x-1,y)
void print_path(int x,int y){ //打印路径:从(0,0)到(29,49),递归回溯。
if(x==0 && y==0) //回溯到了起点,递归结束,返回
return;
if(pre[x][y]=='D') print_path(x-1,y); //回溯,往上 U
if(pre[x][y]=='L') print_path(x, y+1); //回溯,往右 R
if(pre[x][y]=='R') print_path(x, y-1);
if(pre[x][y]=='U') print_path(x+1,y);
printf("%c",pre[x][y]); //最后打印的是终点
}
void bfs(){
node start; start.x=0; start.y=0;
vis[0][0]=1; //标记起点被搜过
queue<node>q; //注意这个队列是结构体队列,直接输入指针即可
q.push(start); //把第一个点放进队列,开始BFS
while(!q.empty()){
node now=q.front();//需要定义一个新结点便于多次循环。
q.pop();
if(now.x==29 && now.y==49){ //判断终止条件
print_path(29,49);
//打印完整路径,从终点回溯到起点,打印出来是从起点到终点的正序
return;
}
for(int i=0;i<4;i++){
node next;
next.x = now.x+dir[i][0];
next.y = now.y+dir[i][1];
if(next.x<0||next.x>=30||next.y<0||next.y>=50)//找出不符合的条件
continue;
if(vis[next.x][next.y]==1 || mp[next.x][next.y]=='1') //撞墙了,显然走不通
continue;//跳过此次循环
vis[next.x][next.y]=1;
pre[next.x][next.y] = k[i]; //记录点(x,y)的前驱,便于打印出最终路径
q.push(next);
}
}
}
int main(){
for(int i=0;i<30;i++) cin >> mp[i];
bfs();
}