Shared code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
char dk[4]={'D','R','U','L'};
int dist[1005][1005];
int vis[1005][1005];
char path[1005][1005];
pair<int,int> parent[1005][1005];
bool flag=false;

bool borderpoint(int x,int y,vector<vector<char>> v,int n,int m) {
    if(x==0 || x==n-1 || y==0 || y==m-1)
    return true;
    else
    return false;    

}
bool isPossible(int x,int y, vector<vector<char>> v,int n,int m) {
    if(x>=0 && x<n && y>=0 && y<m && v[x][y]!='M' && v[x][y]!='#')
    return true;
    else
    return false;
    
}
string shortPathEscape(int n,int m,vector<vector<char>> v) {
    int si,sj;
    string pathdir;

    vector<pair<int,int>> mon;
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            if(v[i][j]=='M') {
                mon.pb({i,j});
            } else if(v[i][j]=='A') {
                si=i;
                sj=j;
            }
        }
    }

    if(mon.size()==0) {
        flag=true;
        return pathdir;
    }

    memset(vis,0,sizeof(vis));
    queue<pair<int,int>> q;
    
    for(int i=0;i<mon.size();i++) {
        q.push({mon[i].first,mon[i].second});
        dist[mon[i].first][mon[i].second]=0;
    }

    while(!q.empty()) {
        pair<int,int> p=q.front();
        q.pop();

        int x=p.first;
        int y=p.second;

        for(int i=0;i<4;i++) {
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(vis[nx][ny]!=1) {
                if(!isPossible(nx,ny,v,n,m)) continue;

                if(dist[nx][ny]>dist[x][y]+1 || dist[nx][ny]==-1) {
                    dist[nx][ny]=dist[x][y]+1;
                    vis[nx][ny]=1;
                    q.push({nx,ny});
                }
            }
        }
    }

    int ei,ej;

    memset(vis,0,sizeof(vis));
    q.push({si,sj});

    dist[si][sj]=0;

    if(borderpoint(si,sj,v,n,m)) {
        flag=true;
        return pathdir;
    }

    while(!q.empty()) {
        pair<int,int> p=q.front();
        q.pop();
        int x=p.first;
        int y=p.second;
        
        for(int i=0;i<4;i++) {
            int nx=x+dx[i];
            int ny=y+dy[i];

            // cout<<"tea2"<<endl;
            if(vis[nx][ny]!=1) {
                if(!isPossible(nx,ny,v,n,m)) continue;
                
                if(dist[nx][ny]>dist[x][y]+1 || dist[nx][ny]==-1) {
                    dist[nx][ny]=dist[x][y]+1;
                    vis[nx][ny]=1;
                    q.push({nx,ny});
                    parent[nx][ny]={x,y};
                    path[nx][ny]=dk[i];
                    
                    if(borderpoint(nx,ny,v,n,m)) {
                        flag=true;
                        ei=nx;
                        ej=ny;
                        break;
                    }
                }
            }
        }

        if(flag)
        break;
    }
    
    if(flag) {
        pair<int,int> ed={ei,ej}, start={si,sj};
        for(auto i=ed;i!=start;i=parent[i.first][i.second]) {
            pathdir+=path[i.first][i.second];
        }
    
        reverse(pathdir.begin(),pathdir.end());
    }
    return pathdir;

}



int main() {
    memset(dist,-1,sizeof(dist));
    int n,m;
    cin>>n>>m;
    vector<vector<char>> v(n,vector<char> (m));
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            cin>>v[i][j];
        }
    }
    
    string s=shortPathEscape(n,m,v);

    if(!flag) {
        cout<<"NO"<<endl;
    } else {
        cout<<"YES"<<endl;
        cout<<s.size()<<endl;
        cout<<s<<endl;
    }
    return 0;
}