/*问题描述
学霸抢走了大家的作业，班长为了帮同学们找回作业，决定去找学霸决斗。但学霸为了不要别人打扰，住在一个城堡里，城堡外面是一个二维的格子迷宫，要进城堡必须得先通过迷宫。因为班长还有妹子要陪，磨刀不误砍柴功，他为了节约时间，从线人那里搞到了迷宫的地图，准备提前计算最短的路线。可是他现在正向妹子解释这件事情，于是就委托你帮他找一条最短的路线。
输入格式
第一行两个整数n， m，为迷宫的长宽。
接下来n行，每行m个数，数之间没有间隔，为0或1中的一个。0表示这个格子可以通过，1表示不可以。假设你现在已经在迷宫坐标(1,1)的地方，即左上角，迷宫的出口在(n,m)。每次移动时只能向上下左右4个方向移动到另外一个可以通过的格子里，每次移动算一步。数据保证(1,1)，(n,m)可以通过。
输出格式
第一行一个数为需要的最少步数K。
第二行K个字符，每个字符∈{U,D,L,R},分别表示上下左右。如果有多条长度相同的最短路径，选择在此表示方法下字典序最小的一个。
样例输入
Input Sample 1:
3 3
001
100
110
Input Sample 2:
3 3
000
000
000
样例输出
Output Sample 1:
4
RDRD
Output Sample 2:
4
DDRR
数据规模和约定
有20%的数据满足：1<=n,m<=10
有50%的数据满足：1<=n,m<=50
有100%的数据满足：1<=n,m<=500。
*/
#include
#include
#define UP 1
#define DOWN 2
#define RIGHT 3
#define LEFT 4
//起点 终点
int route(int n,int m,char (*map)[501]);
void result(int n,int m,int position ,char (*map)[501]);
char picture[501][501];
char picture_mark[501][501]={0};
int process_record[2][250001]={0};
char stack[250001];
int main(){
int n,m,i,position;
scanf("%d",&n);
scanf("%d",&m);
for(i=0;i<n;i++){
scanf("%s",picture[i]);
}
position=route(n,m,picture);
result(n,m,position,picture);
return 0;
}
int route(int n,int m,char (*map)[501])
{
int i,j,k,x,y;
int position_x,position_y; //搜索顺序 URLD
int last_x,last_y;
int where_p=0,where_q=0,transition=0,transition_record=0;
process_record[0][0]=0;
process_record[1][0]=0;
picture_mark[0][0]=-1; //初始化标记
while(1){
x=process_record[0][where_p];
y=process_record[1][where_p];
// printf("12 %d %d\n",where_p,where_q);
if(x==(n-1)&&y==(m-1)){break;}
if(map[x-1][y]=='0'&picture_mark[x-1][y]==0&&(x-1)>=0){
where_q++;
process_record[0][where_q]=x-1;
process_record[1][where_q]=y;
picture_mark[x][y+1]=-1;
}
if(map[x][y+1]=='0'&&picture_mark[x][y+1]==0&&(y+1)<m){
where_q++;
process_record[0][where_q]=x;
process_record[1][where_q]=y+1;
picture_mark[x][y+1]=-1;
}
if(map[x][y-1]=='0'&&picture_mark[x][y-1]==0&&(y-1)>=0){
where_q++;
process_record[0][where_q]=x;
process_record[1][where_q]=y-1;
picture_mark[x][y-1]=-1;
}
if(map[x+1][y]=='0'&&picture_mark[x+1][y]==0&&(x+1)<n){ //字符0
where_q++;
process_record[0][where_q]=x+1;
process_record[1][where_q]=y;
picture_mark[x+1][y]=-1; //遍历标记
}
where_p++;
}
return where_p;
}
//逆向搜索结果
void result(int n,int m,int position ,char (*map)[501]){
int i,j;
int difference_x,difference_y;
int start=0,position_q,position_num;
position_num=position;
position_q=position-1;
while(1){
difference_x=process_record[0][position]-process_record[0][position_q];
difference_y=process_record[1][position]-process_record[1][position_q];
if(difference_x==-1&&difference_y==0){ //反着来相邻的只会有一个
stack[start]='U';
start++;
position=position_q;
}
else if(difference_x==0&&difference_y==-1){
stack[start]='L';
start++;
position=position_q;
}
else if(difference_x==0&&difference_y==1){
stack[start]='R';
start++;
position=position_q;
}
else if(difference_x==1&&difference_y==0){
stack[start]='D';
start++;
position=position_q;
}
if(position==0){break;}
position_q--;
}
//输出
start--;
printf("%d\n",start+1);
for(i=start;i>=0;i--){
printf("%c",stack[i]);
}
return ;
}
