我们可以总结：当只需要求出最短路径是多少是，我们正向bfs就可以了，而当需要求出最短路径的走法时，我们就需要反向bfs，用dist数组或pre数组来更新路径

/*
如果从起点到终点BFS，无法根据当前步骤得出下一步向哪里走(因为可能有多个解)
因为这是从起点开始，对起点位置的累计，只能得出当前点到达起点有多远
所以可以反向BFS，从终点向起点BFS，更新dist[]，再根据dist[]的值确定正确路径
*/
#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef pair<int, int>PII;

const int N = 1010;

int n, m;
char g[N][N];
bool st[N][N];
int dist[N][N];
int dx[] = {1, 0, 0, -1};
int dy[] = {0, -1, 1, 0};
char dir[] = {'D', 'L', 'R', 'U'};

void bfs(int sx, int sy)
{
    memset(dist, 0x3f, sizeof dist);
    dist[sx][sy] = 0;
    queue<PII>q;
    q.push({sx, sy});
    st[sx][sy] = true;
    while(q.size())
    {
        auto t = q.front();
        q.pop();

        for(int i = 0; i < 4; i ++ )
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= m) continue;
            if(g[a][b] == '1') continue;
            if(st[a][b]) continue;
            st[a][b] = true;
            if(dist[a][b] > dist[t.x][t.y] + 1)
            {
                dist[a][b] = dist[t.x][t.y] + 1;
                q.push({a, b});
            }
        }
    }
}

int main()
{
    n = 30, m = 50;
    for(int i = 0; i < n; i ++ ) cin >> g[i];
    int sx = n - 1, sy = m - 1;
    bfs(sx, sy);

    string res = "";
    int x = 0, y = 0;
    while(x != n - 1 || y != m - 1)
    {
        for(int i = 0; i < 4; i ++ )
        {
            int a = x + dx[i], b = y + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= m) continue;
            if(g[a][b] == '1') continue;
            if(dist[a][b] + 1 == dist[x][y])  // 因为dist记录的是终点到起点的路径长度
            {
                x = a, y = b;
                res += dir[i];
                break;  // 一定要break掉
            }
        }
    }
    cout << res << endl;
    return 0;
}