Abandoned warehouse

#include <bits/stdc++.h>

using namespace std;

const vector<tuple<int, int, char>> directions = {{-1, 0, 'U'}, {1, 0, 'D'}, {0, -1, 'L'}, {0, 1, 'R'}};

bool bfs(const vector<string>& warehouse, pair<int, int> start, pair<int, int> end, vector<vector<bool>>& visited, vector<vector<pair<int, int>>>& parent) {
    int n = warehouse.size();
    int m = warehouse[0].size();
    
    queue<pair<int, int>> q;
    q.push(start);
    visited[start.first][start.second] = true;

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        
        if (make_pair(x, y) == end) return true;

        for (const auto& [dx, dy, move] : directions) {
            int nx = x + dx, ny = y + dy;
            
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && warehouse[nx][ny] != '#') {
                visited[nx][ny] = true;
                q.push({nx, ny});
                parent[nx][ny] = {x, y};  
            }
        }
    }

    return false;
}

int main() {
    // Input
    int n, m;
    cin >> n >> m;
    
    vector<string> warehouse(n);
    pair<int, int> start, end;
    
    for (int i = 0; i < n; ++i) {
        cin >> warehouse[i];
        for (int j = 0; j < m; ++j) {
            if (warehouse[i][j] == 'A') start = {i, j};
            if (warehouse[i][j] == 'B') end = {i, j};
        }
    }

    vector<vector<bool>> visited(n, vector<bool>(m, false));
    vector<vector<pair<int, int>>> parent(n, vector<pair<int, int>>(m, {-1, -1}));

    if (bfs(warehouse, start, end, visited, parent)) {
        cout << "YES\n";
        
        string path;
        pair<int, int> current = end;
        
        while (current != start) {
            auto [px, py] = parent[current.first][current.second];
            for (const auto& [dx, dy, move] : directions) {
                if (px + dx == current.first && py + dy == current.second) {
                    path.push_back(move);
                    break;
                }
            }
            current = {px, py};
        }

        reverse(path.begin(), path.end());

        cout << path.length() << '\n';
        cout << path << '\n';
    } else {
        cout << "NO\n";
    }

    return 0;
}

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

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED