jFoS1q - Online C++ Compiler & Debugging Tool

#include <bits/stdc++.h>

typedef long long ll;

#define fi first
#define se second
#define pii pair<ll, ll>

using namespace std;
const int N = 1e3 + 5;

ll n, m, stx, sty;
char a[N][N];
ll vis[N][N], vism[N][N];
ll tx[] = {-1, 0, 0, 1};
ll ty[] = {0, -1, 1, 0};
ll ai[N][N], aj[N][N];
bool ok = false;
queue <pii> mq;

bool inside(ll u, ll v) {
    return (u > 0 && u <= n && v > 0 && v <= m);
}

void bfs(ll s1, ll s2) {
    queue <pii> q;
    q.push({s1, s2});
    vis[s1][s2] = 1;
    while (!q.empty()) {
        ll m = mq.size();
        while (m--) {
            ll mx = mq.front().fi;
            ll my = mq.front().se;
            mq.pop();
            for (int i = 0; i < 4; i++) {
                ll mu = mx + tx[i];
                ll mv = my + ty[i];
                if (!inside(mu, mv) || a[mu][mv] == '#'|| vism[mu][mv])
                    continue;
                vism[mu][mv] = vism[mx][my] + 1;
                mq.push({mu, mv});
            }
        }

        ll x = q.front().fi;
        ll y = q.front().se;
        q.pop();
        for (int i = 0; i < 4; i++) {
            ll u = x + tx[i];
            ll v = y + ty[i];
            if (!inside(u, v) || a[u][v] == '#' || vis[u][v] || (vism[u][v] && vism[u][v] <= vis[x][y] + 1))
                continue;
            ai[u][v] = x;
            aj[u][v] = y;
            q.push({u, v});
            vis[u][v] = vis[x][y] + 1;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen("in.inp", "r", stdin);
    // freopen("ou.out", "w", stdout);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }

    vector <pii> ans;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j] == 'A') {
                if (i == n || j == m || i == 1 || j == 1) {
                    cout << "YES\n";
                    cout <<"0";
                    return 0;
                }
                stx = i;
                sty = j;
            }
            if (a[i][j] == 'M') {
                mq.push({i, j});
                vism[i][j] = 1;
            }
            if ((i == n || j == m || i == 1 || j == 1) && a[i][j] == '.') {
                ans.push_back({i, j});
            }
        }
    }

    if (ans.empty()) {
        cout << "NO";
        return 0;
    }

    bfs(stx, sty);

    stack <char> res;
    for (auto it : ans) {
        if (vis[it.fi][it.se] == 0)
            continue;
        ll x = it.fi, y = it.se;
        while (x != stx || y != sty) {
            ll dx = ai[x][y];
            ll dy = aj[x][y];
            if (dx == x - 1)
                res.push('D');
            else if (dx == x + 1)
                res.push('U');
            else if (dy == y - 1)
                res.push('R');
            else if (dy == y + 1)
                res.push('L');
            x = dx;
            y = dy;
        }

        if (res.size() <= n * m) {
            cout << "YES" << "\n" << res.size() << "\n";
            while (!res.empty()) {
                cout << res.top();
                res.pop();
            }
            return 0;
        }
        else res = stack <char> ();
    }

    cout << "NO";
    return 0;
}