labyrinth.cpp

#include <bits/stdc++.h>
//Author : ritchie_s
#define for0(i, n) for (int i = 0; i < (int)(n); ++i) // 0 based indexing
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i) // 1 based indexing
// Short hand for usual tokens
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define sp " "
// Shorthand for commonly used types
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef double ld;
// functions
#define MOD 1000000007
ll min(ll a,int b) { if (a<b) return a; return b; }
ll min(int a,ll b) { if (a<b) return a; return b; }
ll max(ll a,int b) { if (a>b) return a; return b; }
ll max(int a,ll b) { if (a>b) return a; return b; }
ll gcd(ll a,ll b) { if (b==0) return a; return gcd(b, a%b); }
ll lcm(ll a,ll b) { return (a/gcd(a,b))*b; }
string to_upper(string a) { for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A'; return a; }
string to_lower(string a) { for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A'; return a; }
bool prime(ll a) { if (a==1) return 0; for (int i=2;i<=round(sqrt(a));++i) if (a%i==0) return 0; return 1; }
// int gcd = __gcd(a,b) , ll LCM = 1LL*a*b/gcd
//solver fn
void solve(){
    //take input
    ll n , m;
    cin>>n>>m;
    vector<vector<char>> grid(n , vector<char>(m));
    //find hte start and end point
    pair<ll,ll> start , end;
    for0(i,n){
        for0(j,m){
            cin>>grid[i][j];
            if(grid[i][j] == 'A'){
                start = {i,j};
            }
            else if(grid[i][j] == 'B'){
                end = {i,j};
            }
        }
    }
                   // path retracing back from target to start point in bfs
    vector<pair<ll,ll>> dirs = {{-1,0},{1,0},{0,-1},{0,1}}; // U, D, L, R
    vector<char> moves = {'U','D','L','R'};
    vvll vis(n , vll(m,0));
    vector<vector<char>> movetook(n , vector<char>(m , 'X'));
    vector<vector<pair<ll,ll>>> parents(n , vector<pair<ll,ll>>(m , {-1,-1}));
    queue<pair<ll,ll>> q;
    q.push(start);
    vis[start.fi][start.se] = 1;

    bool flag = 0;
    while(!q.empty()){
        auto node = q.front();
        q.pop();
        if(node == end){
            flag = true;
            break;
        }

        ll x = node.fi , y = node.se;
        for(int i = 0 ; i<4 ; i++){
            ll dx = dirs[i].fi;
            ll dy = dirs[i].se;
            ll nx = x + dx , ny = y + dy;
            if(nx>=0  &&  nx<n  &&  ny>=0  && ny<m  &&  vis[nx][ny] != 1  &&  (grid[nx][ny]=='.' || grid[nx][ny]=='B')){
                parents[nx][ny] = {x,y};
                movetook[nx][ny] = moves[i] ;
                vis[nx][ny] = 1;
                q.push({nx,ny});
            }
        }
    }

    if(flag == true){
        cout<<"YES"<<endl;
        string s = "";
        pair<ll,ll> curr = end;
        while(curr != start){
            s += movetook[curr.fi][curr.se];
            curr = parents[curr.fi][curr.se];
        }

        cout<<s.size()<<endl;
        reverse(all(s));
        cout<<s<<endl;
    }
    else{
        cout<<"NO"<<endl;
    }

}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    cout << fixed;
    solve();
    return 0;
}