[CSES] Labyrinth

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];

    pll st, e;
    rep(i, n) {
        rep(j, m) {
            if (s[i][j] == 'A') st = { i,j };
            else if (s[i][j] == 'B') e = { i,j };
        }
    }

    vector<vpll> save(n, vpll(m, { -1,-1 }));
    vvll vis(n, vll(m, 0));
    function <void(pll)> bfs = [&](pll node) {
        queue<pll> q;
        q.push(node);

        while (sz(q)) {
            auto cur = q.front();
            q.pop();

            ll x = cur.f, y = cur.s;
            vis[x][y] = 1;

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

    if (vis[e.f][e.s]) {
        cout << "YES\n";

        string ans;
        for (pll cur = e; cur != st; cur = save[cur.f][cur.s]) {
            pll p = save[cur.f][cur.s];
            ans.pb(dir(p.f, p.s, cur.f, cur.s));
        }

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

}