Cod sursă (job #769273)

#include <bits/stdc++.h>
//Soltan Cristian
#define fri(a, b) for (int i = (a); i < (b); ++i)
#define frj(a, b) for(int j = a; j < b; j++)
#define frk(a, b) for(int k = a; k < b; k++)
#define frm(a, b, i) for(int i = b; i >= a; i--)
#define ll long long
#define all(x) x.begin(), x.end()
#define mod 1000000007
#define pb push_back
#define st first
#define nd second
#define sz(x) (ll)x.size()
#define rall(x) x.rbegin(), x.rend()
#define ct(x) cout << x
#define cts(x) cout << x << ' '
#define ctn(x) cout << x << '\n'
#define Y cout << "YES" << '\n'
#define N cout << "NO" << '\n'
using namespace std;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vb = vector<bool>;
using ml = map<ll, ll>;
using vii = vector<vector<int>>;
using vll = vector<vector<ll>>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template <typename T>void read(T n, vector<T> &a){fri(0, n){cin >> a[i];}}
template<typename T>void print(T n, T m, vector<vector<T>> &dp){fri(0, n){ct('\n');frj(0, m){ct(setw(5));cts(dp[i][j]);}}}
 
 
const int mxa = 1e9 + 1;
// string __fname = "freelancing";  
// ifstream in(__fname + ".in"); 
// ofstream out (__fname + ".out"); 
// #define cin in 
// #define cout out
 
vector<vector<char>> lab; 
vector<pair<int, int>> monsters;
int stX = 0, stY = 0;
int n, m;
vector<vector<vector<int>>> p;

bool valid(int x, int y){
    if(x >= 0 && y >= 0 && x < n && y < m && lab[x][y] != '#') return true;
    return false;
}
bool validHuman(int x, int y, int time){
    if(x >= 0 && y >= 0 && x < n && y < m && lab[x][y] != '#') {
        for(int i = 0; i < sz(monsters); i++){
            if(p[i][x][y] <= time){
                return false;
            }
        }
        return true;
    }
    return false;
}

string direction(int x, int y){
    if(x == -1 && y == 0){
        return "D";
    }
    if(x == 0 && y == 1){
        return "L";
    }
    if(x == 1 && y == 0){
        return "U";
    }
    else return "R";
}

void solve(){
    cin >> n >> m;
    lab = vector<vector<char>>(n, vector<char>(m));
    for(int i =0; i < n; i++ ){
        for(int j = 0; j < m; j++){
            char x;
            cin >> x;
            if(x == 'M'){
                monsters.push_back({i, j});
            }
            if(x == 'A'){
                if(i == 0 || i == n - 1 || j == 0 || j == m - 1){
                    Y;
                    cout << 0 << '\n';
                    return;
                }
                stX = i;
                stY = j;
            }
            lab[i][j] = x;
        }
    }
    p = vector<vector<vector<int>>>(sz(monsters), vector<vector<int>>(n, vector<int>(m, INT_MAX)));
    for(int i = 0; i < sz(monsters); i++){
        queue<pair<int,int>> q;
        p[i][monsters[i].first][monsters[i].second] = 0;
        q.push({monsters[i].first, monsters[i].second});
        while(!q.empty()){
            int u = q.front().first;
            int v = q.front().second;
            q.pop();
            for(int j = 0; j < 4; j++){
                if(!valid(u + dx[j], v + dy[j])) continue;
                if(p[i][u + dx[j]][v + dy[j]] > p[i][u][v] + 1){
                    p[i][u + dx[j]][v + dy[j]] = p[i][u][v] + 1;
                    q.push({u + dx[j], v + dy[j]});
                }
            }
        }
    }
    queue<pair<int,int>> q;
    vector<vector<int>> dp(n, vector<int>(m, INT_MAX));
    dp[stX][stY] = 0;
    q.push({stX, stY});
    bool pos = false;
    int finX = 0, finY = 0;
    while(!q.empty()){
        int u = q.front().first;
        int v = q.front().second;
        q.pop();
        for(int j = 0; j < 4; j++){
            if(!validHuman(u + dx[j], v + dy[j], dp[u][v] + 1)) continue;
            if(dp[u + dx[j]][v + dy[j]] > dp[u][v] + 1){
                if(u + dx[j] == 0 || u + dx[j] == n - 1 || v + dy[j] == 0 || v + dy[j] == m - 1){
                    finX = u + dx[j];
                    finY = v + dy[j];
                    pos = true;
                }
                dp[u + dx[j]][v + dy[j]] = dp[u][v] + 1;
                q.push({u + dx[j], v + dy[j]});
            }
        }
    }
    if(!pos){
        cout << "NO\n";
        return;
    }
    Y;
    // for(auto i : dp){
    //     for(auto j : i){
    //         if(j > 100){
    //             cout << setw(5) << -1<< ' ';
    //         }
    //         else cout << setw(5) << j << ' ';
    //     }
    //     cout << '\n';
    // }
    cout << dp[finX][finY] << '\n';
    int rs = dp[finX][finY];
    int x = finX, y = finY;
    string ans = "";

    while(rs > 0){
        // cout << rs << '\n';
        fri(0, 4){
            if(!valid(x + dx[i], y + dy[i])) continue;
            if(dp[x + dx[i]][y + dy[i]] == rs - 1){
                rs--;
                ans += direction(dx[i], dy[i]);
                x = x + dx[i];
                y = y + dy[i];
                // cout << x << ' ' << y << '\n';
                break; 
            }
        }
    }
    reverse(all(ans));
    cout << ans << '\n';

    
    
}
 
 
 
int main()
{   
    // ios_base::sync_with_stdio(0); cin.tie(0); ct(fixed); ct(setprecision(10)); 
    // int t;
    // cin >> t;
    // while(t--)
        solve();
    return 0;
}