Abandoned warehouse

from collections import deque
n, m = map(int, input().split())
g = [[] for _ in range(n * m)]

start, finish = -1, -1

s_prev = ''
s = ''

for i in range(n):
    s_prev = s
    s = input()
    for j in range(m):
        if s[j] == "#":
            continue
        if i != 0 and s_prev[j] != '#':
            g[i * m + j].append((i - 1) * m + j)
            g[(i - 1) * m + j].append(i * m + j)
        if j != 0 and s[j - 1] != '#':
            g[i * m + j].append(i * m + j - 1)
        if j != m - 1 and s[j + 1] != '#':
            g[i * m + j].append(i * m + j + 1)

        if s[j] == 'A':
            start = i * m + j
        elif s[j] == 'B':
            finish = i * m + j

dist = [-1] * (n * m)
parent = [-1] * (n * m)

def bfs(v):
    global g, dist
    queue = deque([v])
    while queue:
        node = queue.popleft()
        for w in g[node]:
            if dist[w] == -1 or dist[node] + 1 < dist[w]:
                parent[w] = node
                dist[w] = dist[node] + 1
                queue.append(w)


dist[start] = 0
bfs(start)

if dist[finish] == -1:
    print("NO")
else:
    print("YES")
    print(dist[finish])
    path = []
    path.append(finish)
    v = finish
    while parent[v] != start:
        path.append(parent[v])
        v = parent[v]
    path.append(start)
    path.reverse()
    for i in range(1, len(path)):
        if path[i] == path[i - 1] + 1:
            print('R', end='')
        elif path[i] == path[i - 1] - 1:
            print('L', end='')
        elif path[i] < path[i - 1]:
            print('U', end='')
        else:
            print('D', end='')

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

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