[CSES] Monsters

ll dx[4] = { 1,-1,0,0 };
ll dy[4] = { 0,0,1,-1 };
char dir(ll xf, ll yf, ll xt, ll yt) {
    if (xf == -1 || yf == -1 || xt == -1 || yt == -1)
        return '?';

    if (xt == xf - 1 && yt == yf)return 'U';
    else if (xt == xf + 1 && yt == yf)return 'D';
    else if (xt == xf && yt == yf - 1)return 'L';
    else if (xt == xf && yt == yf + 1)return 'R';

    return '?';
}
void solve() {
    ll n, m;
    cin >> n >> m;

    vector<string> s(n);
    rep(i, n) cin >> s[i];

    function <vvll(vpll)> multisource_bfs = [&](vpll nodes) {
        vvll dis(n, vll(m, inf)), vis(n, vll(m, 0));
        queue<pll> q;
        for (auto& x : nodes) dis[x.f][x.s] = 0, vis[x.f][x.s] = 1, q.push(x);

        while (sz(q)) {
            auto cur = q.front();
            q.pop();
            vis[cur.f][cur.s] = 1;

            rep(k, 4) {
                ll x = cur.f + dx[k], y = cur.s + dy[k];
                if (x >= 0 && x < n && y >= 0 && y < m) {
                    if (!vis[x][y] && s[x][y] != '#') {
                        dis[x][y] = dis[cur.f][cur.s] + 1;
                        vis[x][y] = 1;
                        q.push({ x, y });
                    }
                }
            }
        }

        return dis;
        };

    vpll me, monster;
    rep(i, n) {
        rep(j, m) {
            if (s[i][j] == 'A') me.pb({ i,j });
            else if (s[i][j] == 'M') monster.pb({ i, j });
        }
    }

    vvll dis_me = multisource_bfs(me);
    vvll dis_monster = multisource_bfs(monster);

    rep(i, n) {
        rep(j, m) {
            if (dis_me[i][j] == inf) s[i][j] = '#';
            else if (dis_me[i][j] >= dis_monster[i][j]) {
                s[i][j] = '#';
            }
        }
    }

    debug(s);

    queue<pll> q;
    q.push({ me[0].f, me[0].s });

    pll et = { -1 , -1 };
    vvll vis(n, vll(m, 0));
    vector<vpll> save(n, vpll(m, { -1, -1 }));
    while (sz(q)) {
        auto cur = q.front();
        q.pop();
        vis[cur.f][cur.s] = 1;

        if (cur.f == 0 || cur.f == n - 1 || cur.s == 0 || cur.s == m - 1) {
            et = cur;
            break;
        }

        rep(k, 4) {
            ll x = cur.f + dx[k], y = cur.s + dy[k];
            if (x >= 0 && x < n && y >= 0 && y < m) {
                if (!vis[x][y] && s[x][y] == '.') {
                    vis[x][y] = 1;
                    save[x][y] = cur;
                    q.push({ x, y });
                }
            }
        }
    }

    if (et.f == -1) {
        cout << "NO\n";
        return;
    }

    debug(et, me[0]);
    cout << "YES\n";
    string ans;
    for (pll p = et; p.f != -1; p = save[p.f][p.s]) {
        pll pr = save[p.f][p.s];
        if (pr.f == -1) break;
        ans.pb(dir(pr.f, pr.s, p.f, p.s));
    }

    reverse(all(ans));
    cout << sz(ans) << "\n";
    cout << ans << "\n";
}