CSES - Labyrinth

#include <bits/stdc++.h>
using namespace std;

const int maxN = 1005;
char grid[maxN][maxN];
bool visited[maxN][maxN];
int cost[maxN][maxN];
pair<int,int> parent[maxN][maxN];

int dx[4]= {1,0,-1,0};
int dy[4]= {0,1,0,-1};
char direction[4] = {'D','R','U','L'};

int start_x = -1,start_y = -1,end_x = -1,end_y = -1;

void BFS (int n,int m) {
    cost[end_x][end_y] = maxN;
    grid[start_x][start_y] = 0;
    visited[start_x][start_y] = true;
    queue<pair<int,int>> q;
    q.push(make_pair(start_x,start_y));
    while (!q.empty()) {
        int x = q.front().first,y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; ++i) {
            if ((x + dx[i] <= n and y + dy[i] <= m) and (x + dx[i] >= 1 and y + dy[i] >= 1) and (grid[x + dx[i]][y + dy[i]] == '.' or (x + dx[i] == end_x and y + dy[i] == end_y)) and !visited[x + dx[i]][y + dy[i]]) {
                cost[x + dx[i]][y + dy[i]] = cost[x][y] + 1;
                visited[x + dx[i]][y + dy[i]] = true;
                q.push(make_pair(x + dx[i],y + dy[i]));
                parent[x + dx[i]][y + dy[i]] = make_pair(x,y);
            }
        }
    }
}

int main () {
     ios::sync_with_stdio(false);
     cin.tie(nullptr);
     cout.tie(nullptr);
     int T = 1;
     //~ cin >> T;
     for (int test_case = 1; test_case <= T; ++test_case) {
         int n,m;
         cin >> n >> m;
         for (int i = 1; i <= n; ++i) {
             for (int j = 1; j <= m; ++j) {
                 cin >> grid[i][j];
                 if (grid[i][j] == 'A') {
                     start_x = i,start_y = j;
                 }
                 if (grid[i][j] == 'B') {
                     end_x = i,end_y = j;
                 }
             }
         }
         BFS (n,m);
         if (cost[end_x][end_y] == maxN) {
             cout << "NO\n";
             return 0;
         }
         parent[start_x][start_y] = make_pair(-1,-1);
         string ans = "";
         vector<pair<int,int>> path;
         pair<int,int> res = make_pair(end_x,end_y);
         while (res != make_pair(-1,-1)) {
             path.push_back(res);
             res = parent[res.first][res.second];
         }
         reverse(path.begin(),path.end());
         res = make_pair(start_x,start_y);
         for (int i = 0; i < (int) path.size(); ++i) {
             for (int j = 0; j < 4; ++j) {
                 if (res.first + dx[j] == path[i].first and res.second + dy[j] == path[i].second) {
                     ans += direction[j];
                     res = path[i];
                 }
             }
         }
         cout << "YES\n" << cost[end_x][end_y] << '\n' << ans << '\n';
     }
     //cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}