Untitled

mail@pastecode.io avatar
unknown
c_cpp
25 days ago
1.7 kB
1
Indexable
Never
#include <iostream>
#include <queue>
#include <bits/stdc++.h>

using namespace std;

int di[] = {-1, 1, 0, 0};
int dj[] = {0, 0, 1, -1};
char go[] = {'U', 'D', 'R', 'L'};
int d[1005][1005];

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> mat(n);
    for (string & s : mat) {
        cin >> s;
    }
    queue<pair<int,int>> q;
    int si, sj;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (mat[i][j] == 'M') {
                q.push({i, j});
            }
            else if (mat[i][j] == 'A') {
                si = i;
                sj = j;
            }
        }
    }
    q.push({si,sj});
    d[si][sj] = -1;
    
    while(!q.empty()) {
        pair<int, int> c = q.front();
        q.pop();
        if (mat[c.first][c.second] == 'A' && (c.first == 0 || c.first == n-1 || c.second == 0 || c.second == m-1)) {
            cout<<"YES"<<endl;
            string ans;
            int tmp = d[c.first][c.second];
            while(tmp != -1) {
                ans += go[tmp];
                c.first -= di[tmp];
                c.second -= dj[tmp];
                tmp = d[c.first][c.second];
            }
            reverse(ans.begin(), ans.end());
            cout<<ans.size()<<endl;
            cout<<ans;
            return 0;
        }
        for (int i = 0; i < 4; i++) {
            int ti = c.first + di[i],
            tj = c.second + dj[i];
            if (ti < 0 || ti >= n || tj < 0 || tj >= m || mat[ti][tj] != '.' ) continue;
            else {
                mat[ti][tj] = mat[c.first][c.second];
                if (mat[ti][tj] == 'A') d[ti][tj] = i;
                q.push({ti, tj});
            }
        }
    }
    cout<<"NO";
    return 0;
}
Leave a Comment