Abandoned warehouse

import queue

n, m = [int(i) for i in input().split()]
h = n
w = m
maze = []
start_pos = None
end_pos = None
for y in range(h):
    line = input().rstrip("\n")
    maze.append(line)
    if start_pos and end_pos:
        continue
    for x, c in enumerate(line):
        if c == "A":
            start_pos = (x, y)
        elif c == "B":
            end_pos = (x, y)

search_queue = queue.Queue()
search_queue.put((start_pos[0], start_pos[1]))
visited = [[False] * w for _ in range(h)]
visited[start_pos[1]][start_pos[0]] = True
dist = [[(-1, "", (-1, -1))] * w for _ in range(h)]
dist[start_pos[1]][start_pos[0]] = (0, "", (-1, -1))

moves = [(0, 1, "D"), (0, -1, "U"), (1, 0, "R"), (-1, 0, "L")]
found = False
found_dist = -1

while search_queue.qsize() != 0:
    if found:
        break

    i = search_queue.get()
    x, y = i

    for dx, dy, direction in moves:
        new_x = x + dx
        new_y = y + dy
        if new_x < 0 or new_x >= w or new_y < 0 or new_y >= h:
            continue
        if visited[new_y][new_x]:
            continue
        if maze[new_y][new_x] == "#":
            continue

        visited[new_y][new_x] = True
        old_dist, old_dir, _ = dist[y][x]
        dist[new_y][new_x] = (old_dist + 1, direction, (x, y))
        search_queue.put((new_x, new_y))

        if (new_x, new_y) == end_pos:
            found = True
            found_dist = old_dist + 1
            search_queue = queue.Queue()
            break

if found:
    print("YES")
    print(found_dist)
    path = []
    x, y = end_pos
    while True:
        dis, direction, (prev_x, prev_y) = dist[y][x]
        path.append(direction)
        if dis == 0:
            break
        x, y = prev_x, prev_y

    for i in reversed(path):
        print(i, end="")
    print()

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: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

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