Abandoned warehouse

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Queue;
import java.util.Set;

public class AbandonedWarehouse {

    static int n, m;
    static List<List<Integer>> adj;
    static int[] prev;
    static Queue<Integer> q = new ArrayDeque<>();
    static int startNode = 0;
    static int exitNode = 0;

    static int iix(int i, int j) {
        return i * m + j;
    }

    static boolean bfs() {
        while (!q.isEmpty()) {
            int node = q.poll();
            if (node == exitNode) {
                return true;
            }
            for (int s : adj.get(node)) {
                if (prev[s] == -1) {
                    prev[s] = node;
                    q.add(s);
                }
            }
        }
        return false;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        String[] first = in.readLine().trim().split("\\s+");
        n = Integer.parseInt(first[0]);
        m = Integer.parseInt(first[1]);

        char[][] inpt = new char[n][];
        for (int i = 0; i < n; i++) {
            inpt[i] = in.readLine().toCharArray();
        }

        Set<Character> valid = new HashSet<>(Arrays.asList('.', 'A', 'B'));

        adj = new ArrayList<>(n * m);
        for (int i = 0; i < n * m; i++) {
            adj.add(new ArrayList<>());
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int ix = iix(i, j);
                if (!valid.contains(inpt[i][j])) {
                    continue;
                }
                if (inpt[i][j] == 'A') {
                    startNode = ix;
                }
                if (inpt[i][j] == 'B') {
                    exitNode = ix;
                }
                if (i + 1 < n && valid.contains(inpt[i + 1][j])) {
                    adj.get(ix).add(iix(i + 1, j));
                }
                if (i - 1 >= 0 && valid.contains(inpt[i - 1][j])) {
                    adj.get(ix).add(iix(i - 1, j));
                }
                if (j + 1 < m && valid.contains(inpt[i][j + 1])) {
                    adj.get(ix).add(iix(i, j + 1));
                }
                if (j - 1 >= 0 && valid.contains(inpt[i][j - 1])) {
                    adj.get(ix).add(iix(i, j - 1));
                }
            }
        }

        prev = new int[n * m];
        Arrays.fill(prev, -1);

        q.add(startNode);
        boolean found = bfs();

        StringBuilder sb = new StringBuilder();
        if (found) {
            sb.append("YES\n");
            int node = exitNode;
            List<Integer> trace = new ArrayList<>();
            trace.add(node);
            while (node != startNode) {
                node = prev[node];
                trace.add(node);
            }
            sb.append(trace.size() - 1).append('\n');

            node = trace.remove(trace.size() - 1);
            StringBuilder out = new StringBuilder();
            while (!trace.isEmpty()) {
                int next = trace.get(trace.size() - 1);
                if (next > node) {
                    if (next == node + 1) {
                        out.append('R');
                    } else {
                        out.append('D');
                    }
                } else {
                    if (next == node - 1) {
                        out.append('L');
                    } else {
                        out.append('U');
                    }
                }
                node = trace.remove(trace.size() - 1);
            }
            sb.append(out).append('\n');
        } else {
            sb.append("NO\n");
        }
        System.out.print(sb);
    }
}

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

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED