Monsters

#include <algorithm>
#include <climits>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
#define pii pair<int, int>
#define mn 1005
using namespace std;
 
int N, M;
queue<pii> q;
int paths[mn][mn];
pii from[mn][mn];
int oo = INT_MAX;
pii A;
string ans;
bool possible = false;
 
void retrace(pii node) {  // reconstruir desde el nodo final, agregando la dirección del
	                      // nodo previo a un string. Este string quedará
	                      // al revés pero se invertirá antes de la salida.
	pii origin = from[node.first][node.second];
	if (origin == pii(0, 0)) return;
	if (origin.first == node.first + 1) ans.push_back('U');
	if (origin.first == node.first - 1) ans.push_back('D');
	if (origin.second == node.second + 1) ans.push_back('L');
	if (origin.second == node.second - 1) ans.push_back('R');
	retrace(origin);
}
void check(pii origin,
           pii dest) {  // comprobar si se puede viajar al destino considerado
	int pl = paths[origin.first][origin.second];
	if (pl + 1 < paths[dest.first][dest.second]) {
		paths[dest.first][dest.second] = pl + 1;
		q.push(dest);
		from[dest.first][dest.second] = origin;
	}
}
bool mora = false;  // false si bfs de monstruos, true si bfs de A
void bfs() {
	while (!q.empty()) {
		pii loc = q.front(), next;
		q.pop();
		next = loc;
		next.first++;
		check(loc, next);  // recorrer ubicaciones adyacentes
		next = loc;
		next.first--;
		check(loc, next);
		next = loc;
		next.second++;
		check(loc, next);
		next = loc;
		next.second--;
		check(loc, next);
		if (mora &&
		    (loc.first == 1 || loc.second == 1 || loc.first == N || loc.second == M)) {
			cout << "YES" << endl;
			cout << paths[loc.first][loc.second] << endl;
			retrace(loc);
			possible = true;
			return;
		}
	}
}
 
int main() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		string s;
		cin >> s;
		for (int j = 1; j <= M; j++) {
			paths[i][j] = oo;
			if (s[j - 1] == '#') paths[i][j] = 0;
			if (s[j - 1] == 'M') {
				q.push(pii(i, j));
				paths[i][j] = 0;
			}
			if (s[j - 1] == 'A') {
				A.first = i;
				A.second = j;
			}
		}
	}
	bfs();                                // bfs de monstruos
	mora = true;                          // cambiar el siguiente bfs al bfs de A
	from[A.first][A.second] = pii(0, 0);  // dar a retrace una ubicación de terminación
	paths[A.first][A.second] = 0;
	q.push(A);  // preparar el siguiente bfs
	bfs();      // bfs con A
	if (possible) {
		reverse(ans.begin(), ans.end());
		cout << ans << endl;
	} else cout << "NO" << endl;
}

import java.io.*;
import java.util.*;
 
public class monsters {
	public static int[] dX = {1, -1, 0, 0};
	public static int[] dY = {0, 0, 1, -1};
	public static String dirs = "DURL";
	public static int N, M;
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		char[][] grid = new char[N][M];
		for (int i = 0; i < N; i++) { grid[i] = br.readLine().toCharArray(); }
 
		int[][] dist = new int[N][M];             // Grilla de distancias de los monstruos.
		boolean[][] visited = new boolean[N][M];  // Grilla de visitados de los monstruos.
 
		Queue<point> q = new LinkedList<>();
		// Procesar la grilla.
		point start = new point(-1, -1);
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				// Agregar cada monstruo a la cola.
				if (grid[i][j] == 'M') {
					q.add(new point(i, j));
					dist[i][j] = 0;
					visited[i][j] = true;
				}
				if (grid[i][j] == 'A') { start = new point(i, j); }
			}
		}
 
		// Ejecutar un BFS para los monstruos.
		while (!q.isEmpty()) {
			point cur = q.poll();
			int x = cur.x;
			int y = cur.y;
			for (int i = 0; i < 4; i++) {
				// La siguiente ubicación.
				int x1 = x + dX[i];
				int y1 = y + dY[i];
				if (onGrid(x1, y1) && !visited[x1][y1] && grid[x1][y1] != '#') {
					// Marcar la ubicación como visitada.
					visited[x1][y1] = true;
					dist[x1][y1] = dist[x][y] + 1;
					q.add(new point(x1, y1));
				}
			}
		}
 
		// Inicializar para el BFS humano.
		q = new LinkedList<>();
		q.add(new point(start.x, start.y));
		int[][] dist1 = new int[N][M];  // Grilla de distancias del humano.
		dist1[start.x][start.y] = 0;
 
		boolean[][] visited1 = new boolean[N][M];  // Grilla de visitados del
		                                           // humano.
		visited1[start.x][start.y] = true;
 
		// step[i][j] es la dirección del paso que tomamos para alcanzar el punto (i, j).
		char[][] step = new char[N][M];
		// prevLoc[i][j] es el punto previo antes de alcanzar el punto (i, j).
		point[][] prevLoc = new point[N][M];
		prevLoc[start.x][start.y] = new point(-1, -1);
 
		// Ejecutar un BFS para el humano.
		while (!q.isEmpty()) {
			point cur = q.poll();
			int x = cur.x;
			int y = cur.y;
			for (int i = 0; i < 4; i++) {
				// La siguiente ubicación.
				int x1 = x + dX[i];
				int y1 = y + dY[i];
				char d = dirs.charAt(i);
 
				// Se alcanzó una casilla del borde.
				if (!onGrid(x1, y1)) {
					System.out.println("YES");
					System.out.println(dist1[x][y]);
					StringBuilder ans = new StringBuilder();
					// Ir hacia atrás para imprimir todos los pasos.
					while (x != -1) {
						if (prevLoc[x][y].x != -1) { ans.append(step[x][y]); }
						int tmp = x;
						x = prevLoc[x][y].x;
						y = prevLoc[tmp][y].y;
					}
					System.out.println(ans.reverse());
					return;
				}
 
				if (!visited1[x1][y1] && grid[x1][y1] != '#') {
					if (visited[x1][y1] && dist[x1][y1] <= dist1[x][y] + 1) {
						continue;
					}
					// Marcar la ubicación como visitada.
					visited1[x1][y1] = true;
					dist1[x1][y1] = dist1[x][y] + 1;
					q.add(new point(x1, y1));
					prevLoc[x1][y1] = new point(x, y);
					step[x1][y1] = d;
				}
			}
		}
		System.out.println("NO");
	}
 
	// Si el punto está o no en la grilla.
	public static boolean onGrid(int x, int y) {
		return (x >= 0 && x < N && y >= 0 && y < M);
	}
 
	public static class point {
		public int x, y;
 
		public point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

from collections import deque
 
n, m = map(int, input().split())
maze = [input() for _ in range(n)]
 
# grillas de distancia que llevan la cuenta de los pasos mínimos desde monstruos y persona respectivamente
dist_monster = [[float("inf")] * m for _ in range(n)]
dist_person = [[float("inf")] * m for _ in range(n)]
 
# direction[r][c] guarda qué movimiento se usó para alcanzar (r, c)
# se necesita después para reconstruir el camino de escape yendo hacia atrás
direction = [[-1] * m for _ in range(n)]
 
# deltas de movimiento y sus etiquetas de letra
dir_r = [1, 0, -1, 0]
dir_c = [0, 1, 0, -1]
convert = "DRUL"  # Down, Right, Up, Left
 
# mejor celda del borde que la persona puede alcanzar antes que cualquier monstruo
closest_dist = float("inf")
closest_r, closest_c = -1, -1
 
 
def bfs(q, dist):
	# BFS multi-fuente, llena dist con las distancias más cortas desde todas las fuentes en q
	while q:
		r, c = q.popleft()
		for i in range(4):
			next_r, next_c = r + dir_r[i], c + dir_c[i]
			if (
				0 <= next_r < n
				and 0 <= next_c < m
				and maze[next_r][next_c] != "#"  # saltar paredes
				and dist[next_r][next_c] > dist[r][c] + 1  # solo actualizar si es más corto
			):
				dist[next_r][next_c] = dist[r][c] + 1
				direction[next_r][next_c] = i  # registrar el movimiento para reconstruir el camino
				q.append((next_r, next_c))
 
 
def check_valid(r, c):
	# una celda del borde es un escape válido si la persona llega estrictamente antes que cualquier monstruo
	global closest_dist, closest_r, closest_c
	if (
		maze[r][c] != "#"
		and dist_person[r][c] < dist_monster[r][c]  # la persona gana la carrera
		and dist_person[r][c] < closest_dist  # llevar la cuenta del escape más corto
	):
		closest_dist = dist_person[r][c]
		closest_r, closest_c = r, c
 
 
q = deque()
person_r = person_c = -1
 
for i in range(n):
	for j in range(m):
		if maze[i][j] == "A":
			dist_person[i][j] = 0
			person_r, person_c = i, j
		elif maze[i][j] == "M":
			dist_monster[i][j] = 0  # cada monstruo es su propia fuente de BFS
			q.append((i, j))
 
# flood fill desde todos los monstruos a la vez
bfs(q, dist_monster)
 
# flood fill desde la persona
# la grilla direction solo se escribe aquí, así que el BFS de monstruos de arriba la saltea a propósito
q = deque([(person_r, person_c)])
bfs(q, dist_person)
 
# comprobar cada celda del borde para un escape válido
for i in range(n):
	check_valid(i, 0)
	check_valid(i, m - 1)
for j in range(m):
	check_valid(0, j)
	check_valid(n - 1, j)
 
if closest_dist == float("inf"):
	print("NO")
else:
	print("YES")
	print(closest_dist)
 
	# ir hacia atrás desde la celda de escape hasta el inicio usando la grilla direction, y luego invertir
	res = []
	r, c = closest_r, closest_c
	while (r, c) != (person_r, person_c):
		idx = direction[r][c]
		res.append(convert[idx])
		r -= dir_r[idx]
		c -= dir_c[idx]
 
	print("".join(reversed(res)))