CSES – Labyrinth

#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
int n,m,x,y,endx,endy;
char maze[1005][1005], to[1005][1005];
bool vis[1005][1005] = {0};
bool inrange(int x,int y){
    return x>=0 && y>=0 && x<n && y<m;
}
void bfs(int _x,int _y){
    queue<pair<int,int>> q;
    q.push({_x,_y});
    vis[_x][_y] = 1;
    while(!q.empty()){
        int x = q.front().f, y = q.front().s; q.pop();
        if(inrange(x+1,y) && !vis[x+1][y]){
            to[x+1][y] = 'D';
            vis[x+1][y] = 1;
            q.push({x+1,y});
        }
        if(inrange(x,y+1) && !vis[x][y+1]){
            to[x][y+1] = 'R';
            vis[x][y+1] = 1;
            q.push({x,y+1});
        }
        if(inrange(x-1,y) && !vis[x-1][y]){
            to[x-1][y] = 'U';
            vis[x-1][y] = 1;
            q.push({x-1,y});
        }
        if(inrange(x,y-1) && !vis[x][y-1]){
            to[x][y-1] = 'L';
            vis[x][y-1] = 1;
            q.push({x,y-1});
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>maze[i][j];
            if(maze[i][j] == '#') vis[i][j] = 1;
            if(maze[i][j] == 'A') x = i, y = j;
            if(maze[i][j] == 'B') endx = i, endy = j;
        }
    }
    memset(to,'\0',sizeof(to));
    bfs(x,y);
    if(to[endx][endy] == '\0') cout<<"NO\n";
    else{
        int curx = endx, cury = endy;
        vector<char> ans;
        while(maze[curx][cury] != 'A'){
            char dir = to[curx][cury];
            ans.push_back(dir);
            if(dir == 'U') curx++;
            if(dir == 'D') curx--;
            if(dir == 'L') cury++;
            if(dir == 'R') cury--;
        }
        reverse(ans.begin(),ans.end());
        cout<<"YES\n"<<ans.size()<<"\n";
        for(char c : ans) cout<<c;
        cout<<"\n";
    }
    return 0;
}