Shared code

// Muhammad Mirza Fathan
#include <bits/stdc++.h>
#define fr front
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
vector< vector<int> > time_stamp;
map< pair<int,int>, pair<int,int> > parents;
vector< pair<int,int> > monsters;
pair<int,int> start;
pair<int,int> finish;
int n, m;

/* MOVES */

pair<int,int> left(pair<int,int> point) {
	pair<int,int> newpoint = point;
	newpoint.second--;
	return newpoint;
}

pair<int,int> right(pair<int,int> point) {
	pair<int,int> newpoint = point;
	newpoint.second++;
	return newpoint;
}

pair<int,int> up(pair<int,int> point) {
	pair<int,int> newpoint = point;
	newpoint.first--;
	return newpoint;
}

pair<int,int> down(pair<int,int> point) {
	pair<int,int> newpoint = point;
	newpoint.first++;
	return newpoint;
}

/* ****** */

/* CHECK MOVE */

bool isValid(pair<int,int> point, int stopwatch) {
	int y = point.first;
	int x = point.second;
	if(y<0 || y>=n || x<0 || x>=m)
		return false;
	if(time_stamp[y][x]<= stopwatch)
		return false;
	return true;
}

/* ****** */

/* MONSTERS BFS */

void monsters_bfs() {

	queue< pair< pair<int,int>, int> > q;
	for(int i=0; i<monsters.size(); i++) {
		q.push(mp(monsters[i], 0));
	}
	while(!q.empty()) {
		pair<int,int> cur = q.fr().first;
		int curtime = q.fr().second;
		time_stamp[cur.first][cur.second] = curtime;
		q.pop();
		if(isValid(left(cur), curtime+1))
			q.push(mp(left(cur), curtime+1));
		if(isValid(right(cur), curtime+1))
			q.push(mp(right(cur), curtime+1));
		if(isValid(up(cur), curtime+1))
			q.push(mp(up(cur), curtime+1));
		if(isValid(down(cur), curtime+1))
			q.push(mp(down(cur), curtime+1));
	}

}

/* ****** */

/* ESCAPE ALGORITHM */

bool escape(pair<int,int> start) {
	queue< pair< pair<int,int>,int > > q;
	q.push(mp(start, 0));
	while(!q.empty()) {
		pair<int,int> cur = q.fr().first;
		int curtime = q.fr().second;
//		cout << curtime << " " << time_stamp[cur.first][cur.second] << endl;
		//cout << cur.first<<" "<<cur.second << endl;
		q.pop();

		time_stamp[cur.first][cur.second] = curtime;

		if(cur.first==0 || cur.first==n-1 || cur.second==0 || cur.second==m-1) {
	//		cout << "ok" << endl;
			finish = cur;
			return true;
		}
		if(isValid(left(cur), curtime+1)){
			parents[left(cur)] = cur;
			q.push(mp(left(cur), curtime+1));
		}
		if(isValid(right(cur), curtime+1)){
			parents[right(cur)] = cur;
			q.push(mp(right(cur), curtime+1));
		}
		if(isValid(up(cur), curtime+1)) {
			parents[up(cur)] = cur;
			q.push(mp(up(cur), curtime+1));
		}
		if(isValid(down(cur), curtime+1)) {
			parents[down(cur)] = cur;
			q.push(mp(down(cur), curtime+1));
		}
	}
	return false;
}

/* ****** */

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);


	cin >> n >> m;


	vector< pair<int,int> > path;


	time_stamp.resize(n);


	for(int i=0; i<n; i++) time_stamp[i].resize(m);


	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			time_stamp[i][j] = INT_MAX;
		}
	}


	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			char yx; cin >> yx;
			if(yx=='#') time_stamp[i][j] = -1;
			if(yx=='M') monsters.pb(mp(i,j));
			if(yx=='A') start = mp(i,j);
		}
	}

	/* MONSTERS PROCESSING */
	monsters_bfs();

	/* ****** */

	/* ESCAPE!! */
	if(escape(start)) {
		time_stamp.clear();
		monsters.clear();
		cout << "YES" << endl;
	//	cout << finish.first << " " << finish.second << endl;
		//cout << start.first << " " << start.second << endl;
/*		for(map< pair<int,int>, pair<int,int> > ::const_iterator it = parents.begin();
    it != parents.end(); ++it)
{
    std::cout << it->first.first << " " << it->first.second << "->" << it->second.first << " " << it->second.second << "\n";
}*/
		while(finish!=start) {
			path.pb(finish);
		//	cout << finish.first << " " << finish.second << endl;
			finish = parents[finish];
		//	cout << finish.first << " " << finish.second << endl;
		}
		path.pb(start);
		int len = path.size();
		cout << len-1 << endl;
		for(int i=len-2; i>=0; i--) {
			int ychange = path[i].first - path[i+1].first;
			int xchange = path[i].second - path[i+1].second;
			if(ychange==1) {
				cout << 'D';
			} else if(ychange==-1) {
				cout << 'U';
			} else if(xchange==1) {
				cout << 'R';
			} else if(xchange==-1) {
				cout << 'L';
			}
		} cout << endl;
		return 0;

	}

	cout << "NO" << endl;

  return 0;
}