Both the codes in Java and Python TLE on CSES for same test cases (7-10). Please help me resolve this issue.

Java:

    static void solve(FastReader sc) {
        int n = sc.nextInt(), m = sc.nextInt();
        char mat[][] = new char[n][m];
        char dir[][] = new char[n][m];
        fill2D(dir, '#');
        int si = 0, sj = 0;
        for (int i = 0; i < n; i++) {
            char a[] = sc.next().toCharArray();
            for (int j = 0; j < m; j++) {
                if (a[j] == 'A') {
                    si = i;
                    sj = j;
                } else if (a[j] == 'B') {
                    endi = i;
                    endj = j;
                }
            }
            mat[i] = a;
        }
        
        boolean f = false;
        Queue<pair> q = new LinkedList<>();
        q.offer(new pair(si, sj));
        while (!q.isEmpty()) {
            pair tmp = q.poll();
            // System.out.println(tmp);
            if (tmp.x == endi && tmp.y == endj) {
                f = true;
                break;
            }
            mat[tmp.x][tmp.y] = '#';

            int nx, ny;
            // Left

            nx = tmp.x;
            ny = tmp.y - 1;
            if (!(nx < 0 || nx >= n || ny < 0 || ny >= m || mat[nx][ny] == '#')) {
                q.offer(new pair(nx, ny));
                dir[nx][ny] = 'L';
            }

            // Right

            nx = tmp.x;
            ny = tmp.y + 1;
            if (!(nx < 0 || nx >= n || ny < 0 || ny >= m || mat[nx][ny] == '#')) {
                q.offer(new pair(nx, ny));
                dir[nx][ny] = 'R';
            }

            // Up
            nx = tmp.x - 1;
            ny = tmp.y;
            if (!(nx < 0 || nx >= n || ny < 0 || ny >= m || mat[nx][ny] == '#')) {
                q.offer(new pair(nx, ny));
                dir[nx][ny] = 'U';
            }
            // Down
            nx = tmp.x + 1;
            ny = tmp.y;
            if (!(nx < 0 || nx >= n || ny < 0 || ny >= m || mat[nx][ny] == '#')) {
                q.offer(new pair(nx, ny));
                dir[nx][ny] = 'D';
            }
            // System.out.println(q);
        }
        StringBuilder s = new StringBuilder();
        if (!f)
        System.out.println("NO");
        else {
            int nx = endi, ny = endj;
            while(nx!=si || ny!=sj)
            {
                s.append(dir[nx][ny]);
                switch(dir[nx][ny])
                {
                    case 'L':{ny++;break;}
                    case 'R':{ny--;break;}
                    case 'U':{nx++;break;}
                    case 'D':{nx--;break;}
                }
            }
            s.reverse();
            System.out.println("YES");
            System.out.println(s.length());
            System.out.println(s.toString());
        }
        // for (int i = 0; i < n; i++) {
        // for (int j = 0; j < m; j++) {
        // sc.print(dir[i][j]);
        // }
        // sc.println();
        // }
        /*
         * for(int i = 0;i<n;i++) { for(int j = 0; j<m;j++) { sc.print(mat[i][j]); }
         * sc.println(); }
         */

    }

Python :

from collections import deque
n,m = map(int,input().split())
mat = []
si = sj = 0
endi = endj = 0
for i in range(n):
    l = list(input())
    for j in range(m):
        if l[j]=='A':
            si,sj = i,j
        if l[j]=='B':
            endi, endj = i,j
    mat.append(l)

f = False
q = deque()
dir = [["#" for i in range(m)] for i in range(n)]
q.append([si,sj])
while(len(q)!=0):
    tmp = q.popleft()
    if (tmp[0] == endi and tmp[1] == endj):
        f = True
        break
    x = tmp[0]
    y = tmp[1]
    mat[x][y] = '#'
    nx = ny = 0
    
    # Left
    nx = x
    ny = y-1
    if (not(nx < 0 or nx >= n or ny < 0 or ny >= m or mat[nx][ny] == '#')):
        q.append([nx,ny])
        dir[nx][ny] = 'L'
    # Right
    nx = x
    ny = y+1
    if (not(nx < 0 or nx >= n or ny < 0 or ny >= m or mat[nx][ny] == '#')):
        q.append([nx,ny])
        dir[nx][ny] = 'R'
    # Up
    nx = x-1
    ny = y
    if (not(nx < 0 or nx >= n or ny < 0 or ny >= m or mat[nx][ny] == '#')):
        q.append([nx,ny])
        dir[nx][ny] = 'U'
    # Down
    nx = x+1
    ny = y
    if (not(nx < 0 or nx >= n or ny < 0 or ny >= m or mat[nx][ny] == '#')):
        q.append([nx,ny])
        dir[nx][ny] = 'D'

if not f:
    print("NO")
else:
    s = []
    nx,ny = endi, endj
    while nx!=si or ny!=sj:
        s.append(dir[nx][ny])
        c = dir[nx][ny]

        if c=='L':
            ny+=1
        elif c=='R':
            ny-=1
        elif c=='U':
            nx+=1
        else:
            nx-=1
    print("YES")
    print(len(s))
    print(*s[::-1], sep='')