L. Lonely day

#include <bits/stdc++.h>
#define MAXN 2020
#define F first
#define S second
using namespace std;
typedef pair<char,int> pci;

char tab[MAXN][MAXN];
vector<pci> grafo[MAXN*MAXN];
int n, m;

void add_aresta(int al, int ac, int bl, int bc, char vai, char volta){
    grafo[MAXN*al+ac].push_back(pci(vai, MAXN*bl+bc));
    grafo[MAXN*bl+bc].push_back(pci(volta, MAXN*al+ac));
}

int s, r;
int dist[MAXN*MAXN];

void bfs(){

    queue<int> q;
    q.push(r);
    dist[r] = 1;

    while(!q.empty()){
        int v = q.front();

        q.pop();

        //cout << v << endl;
        for(pci edge : grafo[v]){
            int u = edge.S;
            if(dist[u] == 0){
                q.push(u);
                dist[u] = dist[v] + 1;
            }
        }
    }
}



void dfs(int v, vector<char> &caminho){
    if(v == r) return;
    if(dist[v] == 0) return;

    pci prox;
    prox.S =  -1;

    for(pci edge : grafo[v]){
        if( (prox.S == -1) or
            (dist[edge.S] < dist[prox.S]) or
            (dist[edge.S] == dist[prox.S] and edge.F < prox.F)
           ){
            prox = edge;
        }
    }

    caminho.push_back(prox.F);
    dfs(prox.S, caminho);
}

int main(){

    cin.tie(0);
    cin.sync_with_stdio(0);

    cin >> n >> m;

    for(int i = 1; i <= n; i++){
        cin >> (&tab[i][1]);
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(tab[i][j] == 'S') s = i*MAXN + j;
            if(tab[i][j] == 'E') r = i*MAXN + j;
        }
    }

    for(int i = 1; i <= n; i++){
        int ant = -1;

        for(int j = 1; j <= m; j++){
            if(tab[i][j] != 'X'){
                if(ant != -1){
                    add_aresta(i,ant,i,j,'R','L');
                }
                ant = j;
            }
        }
    }

    for(int j = 1; j <= m; j++){
        int ant = -1;

        for(int i = 1; i <= n; i++){
            if(tab[i][j] != 'X'){
                if(ant != -1){
                    add_aresta(ant,j,i,j,'D','U');
                }
                ant = i;
            }
        }
    }


    bfs();

    vector<char> cam = {};
    dfs(s, cam);

    if(cam.size() == 0){
        cout << -1 << endl;
    }else{
        cout << cam.size() << endl;
        for(char x : cam){
            cout << x;
        }
        cout << endl;
    }

}