/*
分析
该题需要输出最短路径长度,还有具体的路线
对于BFS,画个图可以发现:
如果从起点到终点BFS,无法根据当前步骤得出下一步向哪里走(因为可能有多个解)
因为这是从起点开始,对起点位置的累计,只能得出当前点到达起点有多远
所以可以反向BFS,从终点向起点BFS,更新dist[],再根据dist[]的值确定正确路径
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 55;
int dist[N][N]; // 二维数组中记录了大部分点到达起点的步数
string g[N];
int n, m;
int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,-1,1,0 };
char dir[4] = { 'D','L','R','U' }; // 记录方向
void bfs()
{
memset(dist, -1, sizeof dist);
dist[n - 1][m - 1];
queue<pair<int, int> > q;
q.push({ n - 1,m - 1 });
while (q.size())
{
auto tmp = q.front(); // 注意是front()
q.pop();
for (int i = 0; i < 4; i++)
{
int a = tmp.first + dx[i];
int b = tmp.second + dy[i];
if (a >= 0 && a < n && b >= 0 && b < m && dist[a][b] == -1 && g[a][b] == '0')
{
dist[a][b] = dist[tmp.first][tmp.second] + 1;
q.push({ a,b });
}
}
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> g[i];
bfs();
cout << dist[0][0] << endl;
// 再从头枚举路径
string res; // 方向
int x = 0, y = 0; // 起点
while (x != n - 1 || y != m - 1) // xy必须都要达到终点
{
for (int i = 0; i < 4; i++)
{
int a = x + dx[i];
int b = y + dy[i]; // 下一步要走的点
if (a >= 0 && a < n && b >= 0 && b < m)
{
if (g[a][b] == '0' && dist[x][y] == dist[a][b] + 1) // 确保当前点可行,并且连续
{
x = a;
y = b; // 能走就要更新xy
res += dir[i];
break;
// 找到一个合适的点后就要跳出去,不然还会在该点四个方向乱找,实际上应该去下一个点四个方向乱找
}
}
}
}
cout << res;
return 0;
}