Abandoned warehouse

// Problem: Labyrinth
// Contest: CSES - CSES Problem Set
// URL: https://cses.fi/problemset/task/1193
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)
 
/*
 * Author: bubu2006
**/
 
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int n, m;
    cin >> n >> m;
    
    vector<string> a(n);
    for(int i = 0; i < n; i++)
        cin >> a[i];
    
    pair<int, int> st, en;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(a[i][j] == 'A') st = {i, j};
            else if(a[i][j] == 'B') en = {i, j};
        }
    }
    
    vector<vector<int>> dis(n, vector<int>(m, 1e7));
    vector<vector<pair<int, int>>> par(n, vector<pair<int, int>>(m));
    vector<int> dy = {0, 0, -1, 1};
    vector<int> dx = {1, -1, 0, 0};
    
    queue<pair<int, int>> q;
    q.push({st.first, st.second});
    dis[st.first][st.second] = 0;
    
    while(!q.empty()) {
        pair<int, int> cur = q.front();
        int y = cur.first;
        int x = cur.second;
        
        // cerr << y << ' ' << x << '\n';
        q.pop();
        
        if(cur == en) {
            break;
        }
        
        for(int k = 0; k < 4; k++) {
            int ny = y + dy[k];
            int nx = x + dx[k];
            
            if(ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
            if(a[ny][nx] == '#') continue;
            if(dis[ny][nx] != 1e7) continue;
            
            q.push({ny, nx});
            par[ny][nx] = {y, x};
            dis[ny][nx] = dis[y][x] + 1;
        }
    }
    
    if(dis[en.first][en.second] == 1e7) {
        cout << "NO\n";
        return 0;
    }
    
    cout << "YES\n";
    cout << dis[en.first][en.second] << '\n';
    // cout << par[en.first][en.second].first << ' ' << par[en.first][en.second].second << '\n';
    
    string ans = "";
    int y = en.first;
    int x = en.second;
    
    while(true) {
        // cerr << y << ' ' << x << '\n';
        if(a[y][x] == 'A') break;
        
        pair<int, int> p = par[y][x];
        int py = p.first;
        int px = p.second;
        
        int difx = x - px;
        int dify = y - py;
        pair<int, int> dir = {dify, difx};
        
        if(dir == make_pair(0, 1)) {
            ans += 'R';
        } else if(dir == make_pair(0, -1)) {
            ans += 'L';
        } else if(dir == make_pair(1, 0)) {
            ans += 'D';
        } else {
            ans += 'U';
        }
        
        y = py;
        x = px;
    }
    
    reverse(ans.begin(), ans.end());
    cout << ans << '\n';
}

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