Labyrinth

#include <bits/stdc++.h>
 
using namespace std;
 
#define ii pair<int, int>
#define f first
#define s second
#define mp make_pair
 
int n, m;
char A[1000][1000];
bool vis[1000][1000];
 
// previousStep guarda la dirección previa en la que nos movimos para llegar a
// esta celda
int previous_step[1000][1000];
 
// 0 = arriba, 1 = derecha, 2 = abajo, 3 = izquierda
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
string step_dir = "URDL";
 
int main() {
	cin >> n >> m;
 
	queue<ii> q;
	ii begin, end;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> A[i][j];
			if (A[i][j] == 'A') {
				begin = mp(i, j);
			} else if (A[i][j] == 'B') {
				end = mp(i, j);
			}
		}
	}
 
	q.push(begin);
	vis[begin.f][begin.s] = true;
 
	while (!q.empty()) {
		ii u = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			ii v = mp(u.f + dx[i], u.s + dy[i]);
			if (v.f < 0 || v.f >= n || v.s < 0 || v.s >= m) continue;
			if (A[v.f][v.s] == '#') continue;
			if (vis[v.f][v.s]) continue;
			vis[v.f][v.s] = true;
			previous_step[v.f][v.s] = i;
			q.push(v);
		}
	}
 
	if (vis[end.f][end.s]) {
		cout << "YES" << endl;
		vector<int> steps;
		while (end != begin) {
			int p = previous_step[end.f][end.s];
			steps.push_back(p);
			// deshacer el paso previo para volver a la casilla anterior
			// Nótese cómo restamos dx/dy, mientras que antes sumábamos dx/dy
			end = mp(end.f - dx[p], end.s - dy[p]);
		}
		reverse(steps.begin(), steps.end());
 
		cout << steps.size() << endl;
		for (char c : steps) { cout << step_dir[c]; }
		cout << endl;
	} else {
		cout << "NO" << endl;
	}
}

import java.io.*;
import java.util.*;
 
public class cses1193 {
	public static int[] dX = {-1, 0, 0, 1};
	public static int[] dY = {0, -1, 1, 0};
	public static String dirs = "ULRD";
 
	// Coordenadas de los puntos A y B.
	public static point A = new point(-1, -1);
	public static point B = new point(-1, -1);
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		boolean[][] blocked = new boolean[N][M];
		boolean[][] visited = new boolean[N][M];
		int[][] prevMove = new int[N][M];
 
		// Leer la grilla.
		for (int i = 0; i < N; i++) {
			char[] S = br.readLine().toCharArray();
			for (int j = 0; j < M; j++) {
				if (S[j] == '#') {
					blocked[i][j] = true;
				} else {
					blocked[i][j] = false;
					if (S[j] == 'A') { A = new point(i, j); }
 
					if (S[j] == 'B') { B = new point(i, j); }
				}
			}
		}
		Queue<point> q = new LinkedList<>();
		q.add(A);
 
		// BFS empezando desde el punto A.
		while (!q.isEmpty()) {
			point cur = q.poll();
 
			for (int dir = 0; dir < 4; dir++) {
				point next = new point(cur.x + dX[dir], cur.y + dY[dir]);
				// Comprobar si el siguiente punto se puede visitar.
				if (next.x < 0 || next.y < 0 || next.x >= N || next.y >= M) {
					continue;
				}
				if (blocked[next.x][next.y]) { continue; }
				if (visited[next.x][next.y]) { continue; }
				visited[next.x][next.y] = true;
				prevMove[next.x][next.y] = dir;
				q.add(next);
			}
		}
 
		if (visited[B.x][B.y]) {
			pw.println("YES");
			ArrayList<Integer> moves = new ArrayList<>();
 
			// Ahora podemos ir hacia atrás desde B para hallar todos los movimientos que hicimos.
			while ((A.x != B.x) || (A.y != B.y)) {
				int prevDir = prevMove[B.x][B.y];
				moves.add(prevDir);
 
				B.x = B.x - dX[prevDir];
				B.y = B.y - dY[prevDir];
			}
			Collections.reverse(moves);
 
			pw.println(moves.size());
			for (int i : moves) { pw.print(dirs.charAt(i)); }
 
		} else {
			// No podemos alcanzar el punto B.
			pw.println("NO");
		}
		pw.close();
	}
 
	public static class point {
		public int x, y;
		public point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

from collections import deque
 
MAX_N = 1000
STEP_DIR = "URDL"
 
# 0 = arriba, 1 = derecha, 2 = abajo, 3 = izquierda
DX = [-1, 0, 1, 0]
DY = [0, 1, 0, -1]
 
vis = [[False for _ in range(MAX_N)] for _ in range(MAX_N)]
 
# previous_step guarda la dirección previa en la que nos movimos para llegar a esta celda
previous_step = [[-1 for _ in range(MAX_N)] for _ in range(MAX_N)]
 
n, m = map(int, input().split())
 
a = []
begin = []
end = []
 
for i in range(n):
	row = list(input())
	a.append(row)
	for j in range(m):
		if a[i][j] == "A":
			begin = (i, j)
		elif a[i][j] == "B":
			end = (i, j)
 
q = deque()
q.append(begin)
vis[begin[0]][begin[1]] = True
 
while q:
	u = q.popleft()
	for i in range(4):
		v = (u[0] + DX[i], u[1] + DY[i])
 
		if v[0] < 0 or v[0] >= n or v[1] < 0 or v[1] >= m:
			continue
		if a[v[0]][v[1]] == "#":
			continue
		if vis[v[0]][v[1]]:
			continue
 
		vis[v[0]][v[1]] = True
		previous_step[v[0]][v[1]] = i
		q.append(v)
 
if vis[end[0]][end[1]]:
	print("YES")
	steps = []
	while end != begin:
		p = previous_step[end[0]][end[1]]
		steps.append(p)
		# deshacer el paso previo para volver a la casilla anterior
		# nótese cómo restamos DX/DY, mientras que antes sumábamos DX/DY
		end = (end[0] - DX[p], end[1] - DY[p])
 
	steps.reverse()
	print(len(steps))
	print("".join(STEP_DIR[step] for step in steps))
else:
	print("NO")