Labyrinth

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
2.9 kB
7
Indexable
Never
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,b) for(int i = a; i<b; i++)
#define rew(x) for(int i = 0; i<x; i++)
#define deb(x) cout<<"\n"<<#x <<": "<<x<<"\n";
#define seev(v,n) for(int i=0;i<n;i++){int x; cin>>x; v.push_back(x);}
#define endl "\n"

//DEBUGGER
#ifndef ONLINE_JUDGE
    #include<pprint.hpp>
    pprint::PrettyPrinter _printer(std::cerr);
    #define de(...) _printer.compact(true).print('[', #__VA_ARGS__,"] =", __VA_ARGS__)
    #define de2(...) _printer.compact(false).print('[', #__VA_ARGS__,"] =", __VA_ARGS__)
#endif

#ifdef ONLINE_JUDGE // https://github.com/p-ranav/pprint
    #define de(...)
    #define de2(...)
#endif
// DEBUGGER CODE ENDS


int n,m;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
char dc[] = {'U', 'R', 'D', 'L'};

// Input grid
vector<string> v;
// To store from which direction we came from
vector<vector<char>> path;

vector<vector<bool>> vis(1001,vector<bool> (1001,false));
vector<vector<pair<int,int>>> parent;

// To check if it's in the bound, is not visited and is not a wall
bool isValid(int x, int y){
    return ((x>=0 && x<n && y>=0 && y < m) && (!vis[x][y]) && v[x][y] != '#');
}

void bfs(int i, int j){
    queue<pair<int,int>> q;
    q.push({i,j});
    path[i][j] = ';'; // MArking the initial cell
    while(!q.empty()){
        pair<int,int> curr = q.front();
        q.pop();
        vis[curr.first][curr.second] = 1;
        rep(t,0,4){
            int x = curr.first + dx[t];
            int y = curr.second + dy[t];
            if(isValid(x,y)){
               parent[x][y] = curr;
               path[x][y] = dc[t];
               if(v[x][y] == 'B'){
                   return;
               }
               q.push({x,y});
            }
        }
    }
}

void solve(){
    cin>>n>>m;
    rew(n){
        string a; cin>>a;
        v.push_back(a);
    }
  	// Intializing path and parent according to n,m
    path = vector<vector<char>> (n,vector<char> (m, '.'));
    parent = vector<vector<pair<int,int>>> (n,vector<pair<int,int>> (m,{-1,-1}));
    pair<int,int> start,end;
    rep(i,0,n){
        rep(j,0,m){
            if(v[i][j] == 'A'){
                start = {i,j};
            }else if(v[i][j] == 'B'){
                end = {i,j};
            }
        }
    }
    bfs(start.first,start.second);
  	// To check if we ever reached B or not
    if(path[end.first][end.second] == '.'){
        cout<<"NO"; return;
    }
    
    pair<int,int> curr = end;
    string ans = "";
    while(curr != start){
        ans += path[curr.first][curr.second];
        curr = parent[curr.first][curr.second];
    }

    reverse(ans.begin(),ans.end());
    cout<<"YES\n";
    cout<<ans.size()<<endl;
    cout<<ans;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}