Abandoned warehouse

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())
inpt = []
for _ in range(n):
    inpt.append(list(input()))


def iix(i: int, j: int) -> int:
    return i * m + j


exit_node = 0
start_node = 0
valid = set([".", "A", "B"])
adj = [[] for _ in range(n * m)]
for i in range(n):
    for j in range(m):
        ix = iix(i, j)

        if inpt[i][j] not in valid:
            continue
        if inpt[i][j] == "A":
            start_node = ix
        if inpt[i][j] == "B":
            exit_node = ix

        if i + 1 < n and inpt[i + 1][j] in valid:
            adj[ix].append((iix(i + 1, j)))
        if i - 1 >= 0 and inpt[i - 1][j] in valid:
            adj[ix].append((iix(i - 1, j)))
        if j + 1 < m and inpt[i][j + 1] in valid:
            adj[ix].append((iix(i, j + 1)))
        if j - 1 >= 0 and inpt[i][j - 1] in valid:
            adj[ix].append((iix(i, j - 1)))

q = deque([start_node])
prev = [-1] * (n * m)


def bfs() -> bool:
    while q:
        node = q.popleft()
        if node == exit_node:
            return True
        for s in adj[node]:
            if prev[s] == -1:
                prev[s] = node
                q.append(s)

    return False


found = bfs()

if found:
    print("YES")
    node = exit_node
    trace = [node]
    while node != start_node:
        node = prev[node]
        trace.append(node)
    print(len(trace) - 1)

    node = trace.pop()
    out = ""
    while len(trace) > 0:
        next = trace[-1]
        if next > node:
            if next == node + 1:
                out += "R"
            else:
                out += "D"
        else:
            if next == node - 1:
                out += "L"
            else:
                out += "U"
        node = trace.pop()
    print(out)
else:
    print("NO")

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: TIME LIMIT EXCEEDED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: TIME LIMIT EXCEEDED