Giới thiệu
include <iostream>
include <vector>
include <queue>
include <stack>
using namespace std;
const int MAX = 1003;
int n, m;
vector<string> maze(MAX);
vector<vector\<int>> distA(MAX, vector<int>(MAX, -1));
vector<vector\<int>> distM(MAX, vector<int>(MAX, -1));
vector<pair\<int, int>> monsters;
pair<int, int> start;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
char dir[4] = {'D', 'U', 'R', 'L'};
bool isValid(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < m && maze[x][y] != '#';
}
void bfs(queue<pair\<int, int>>& q, vector<vector\<int>>& dist) {
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (isValid(nx, ny) && dist[nx][ny] == -1) {
dist[nx][ny] = dist[x][y] + 1;
q.push({nx, ny});
}
}
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> maze[i];
}
queue<pair<int, int>> q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (maze[i][j] == 'A') {
start = {i, j};
distA[i][j] = 0;
} else if (maze[i][j] == 'M') {
monsters.push_back({i, j});
distM[i][j] = 0;
q.push({i, j});
}
}
}
bfs(q, distM); // BFS for monsters
q.push(start);
bfs(q, distA); // BFS for player
vector<vector<int>> exitDist = distA;
for (auto [x, y] : monsters) {
if (distA[x][y] != -1 && distA[x][y] <= distM[x][y]) {
cout << "NO" << endl;
return 0;
}
}
int ex = -1, ey = -1;
for (int i = 0; i < n; i++) {
if (maze[i][0] == '.' || maze[i][0] == 'A') {
if (distA[i][0] != -1 && (distA[i][0] < distM[i][0] || distM[i][0] == -1)) {
ex = i, ey = 0;
break;
}
}
if (maze[i][m-1] == '.' || maze[i][m-1] == 'A') {
if (distA[i][m-1] != -1 && (distA[i][m-1] < distM[i][m-1] || distM[i][m-1] == -1)) {
ex = i, ey = m-1;
break;
}
}
}
for (int j = 0; j < m; j++) {
if (maze[0][j] == '.' || maze[0][j] == 'A') {
if (distA[0][j] != -1 && (distA[0][j] < distM[0][j] || distM[0][j] == -1)) {
ex = 0, ey = j;
break;
}
}
if (maze[n-1][j] == '.' || maze[n-1][j] == 'A') {
if (distA[n-1][j] != -1 && (distA[n-1][j] < distM[n-1][j] || distM[n-1][j] == -1)) {
ex = n-1, ey = j;
break;
}
}
}
if (ex == -1) {
cout << "NO" << endl;
return 0;
}
cout << "YES" << endl;
vector<char> path;
while (ex != start.first || ey != start.second) {
for (int i = 0; i < 4; i++) {
int nx = ex - dx[i], ny = ey - dy[i];
if (isValid(nx, ny) && distA[nx][ny] == distA[ex][ey] - 1) {
path.push_back(dir[i]);
ex = nx;
ey = ny;
break;
}
}
}
reverse(path.begin(), path.end());
cout << path.size() << endl;
for (char c : path) cout << c;
cout << endl;
return 0;
}