代码：
#include<bits/stdc++.h>
using namespace std;
int n, m;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};
int vis[1005][1005];
char mapa[1005][1005];
bool flag = 0;
int tx, ty, tz;
struct node {
int ax, ay;
} dis[1005][1005], a[1005];
struct node2 {
int x, y;
int step;
};
queue<node2> q;
void bfs1() {
while (!q.empty()) {
node2 now = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int xx = now.x + dx[i];
int yy = now.y + dy[i];
if (xx > 0 && yy > 0 && xx <= n && yy <= m && mapa[xx][yy] != '#' && vis[xx][yy] == 0) {
vis[xx][yy] = now.step + 1;
q.push(node2{xx, yy, now.step + 1});
}
}
}
}
void bfs2(int x, int y) {
q.push(node2{x, y, 0});
while (!q.empty()) {
node2 now = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int xx = now.x + dx[i];
int yy = now.y + dy[i];
if (xx > 0 && yy > 0 && xx <= n && yy <= m && mapa[xx][yy] != '#' && now.step + 1 < vis[xx][yy]) {
dis[xx][yy].ax = now.x;
dis[xx][yy].ay = now.y;
vis[xx][yy] = -2;
if (xx == 1 || yy == 1 || xx == n || yy == m) {
cout << "YES" << endl << now.step + 1 << endl;
tx = xx;
ty = yy;
tz = now.step + 1;
return;
}
q.push(node2{xx, yy, now.step + 1});
}
}
}
cout << "NO";
flag = 1;
}
int main() {
cin >> n >> m;
int x, y;
for (int i = 1; i <= n; i++) {
scanf( "%s", mapa[i] + 1);
for (int j = 1; j <= m; j++) {
if (mapa[i][j] == 'M') {
q.push(node2{i, j, 0});
vis[i][j] = -1;
}
if (mapa[i][j] == 'A')x = i, y = j;
}
}
bfs1();
bfs2(x, y);
int em;
if (flag == 0) {
int xx = tx, yy = ty;
tz++;
em = tz;
while (1) {
a[tz].ax = xx;
a[tz].ay = yy;
tz--;
if (xx == x && yy == y)break;
int t = dis[xx][yy].ay;
xx = dis[xx][yy].ax;
yy = t;
}
}
for (int i = 2; i <= em; i++) {
if (a[i].ax - a[i - 1].ax == 1) {
cout << "D";
}
else if (a[i - 1].ax - a[i].ax == 1) {
cout << "U";
}
else if (a[i].ay - a[i - 1].ay == 1) {
cout << "R";
}
else if (a[i - 1].ay - a[i].ay == 1) {
cout << "L";
}
}
return 0;
}/*
8 8
########
#.....A#
#.######
#......#
#.####.#
#....#.#
#.##.#.#
#..M.#.#*/