BFS-Path-Finding

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define all(x) x.begin(), x.end()
#define ar array
#define ff first
#define ss second
#define PI pair<int, int>
const int inf = 1e9 + 5;

vector<vector<char>> grid;
int n, m;
const int mx = 1e3;
int distm[2001][2001], disth[2001][2001];
pair<PI, char> par[2001][2001];
vector<int> xdir{1, 0, -1, 0}, ydir{0, 1, 0, -1};
vector<char> dir{'D', 'R', 'U', 'L'};
PI st, en;

void init()
{
    cin >> n >> m;
    grid = vector<vector<char>>(n, vector<char>(m));
    queue<PI> q;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> grid[i][j];
            distm[i][j] = inf;
            disth[i][j] = inf;
            if (grid[i][j] == 'M')
            {
                q.push({i, j});
                distm[i][j] = 0;
            }
            else if (grid[i][j] == 'A')
            {
                st = {i, j};
                grid[i][j]='.';
                disth[i][j] = 0;
            }
        }
    }

    auto isSafe = [&](int x, int y) -> bool
    {
        bool isBorder = (x == 0 or y == 0 or x == n - 1 or y == m - 1);
        bool isStar = grid[x][y] == '.';
        return isBorder && isStar;
    };

    auto isvalid = [&](PI X) -> bool
    {
        int i = X.ff, j = X.ss;
        return (i >= 0 and i < n and j >= 0 and j < m and grid[i][j] != '#');
    };

    while (!q.empty())
    {
        PI x = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            PI X = {x.ff + xdir[i], x.ss + ydir[i]};
            if (!isvalid(X) || distm[X.ff][X.ss] != inf)
                continue;
            distm[X.ff][X.ss] = distm[x.ff][x.ss] + 1;
            q.push(X);
        }
    }

    q = {};
    q.push(st);
    bool ok = false;
    while (!q.empty())
    {
        PI x = q.front();
        q.pop();
        if (isSafe(x.ff, x.ss))
        {
            en = x;
            ok = true;
            break;
        }
        for (int i = 0; i < 4; i++)
        {
            PI X = {x.ff + xdir[i], x.ss + ydir[i]};
            if (!isvalid(X) || disth[X.ff][X.ss]!=inf || distm[X.ff][X.ss] <= disth[x.ff][x.ss]+1)
                continue;
            disth[X.ff][X.ss] = disth[x.ff][x.ss] + 1;
            par[X.ff][X.ss] = {x, dir[i]};
            q.push(X);
        }
    }
    if (!ok)
    {
        cout << "NO" << endl;
        return;
    }
    string z;
    while (en != st)
    {
        z += par[en.ff][en.ss].ss;
        en = par[en.ff][en.ss].ff;
    }
    cout << "YES\n";
    reverse(all(z));
    cout << z.size() << "\n";
    cout << z;
}
int32_t main()
{
    init();
    return 0;
}