The problem can be found here: https://cses.fi/problemset/result/1045629/

I've been working on this problem for a week now — I have over 20 submissions. With different methods:

I tried passing the path along a node, which has a TLE on test case 13:

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
 
 
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define F0R(i, a) for(ll i = 0; i < a; i++)
#define f first
#define s second
 
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; //
const ll INF = 1e18; //
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
string ds = "RLDU";
 
const int mxN = 1e3;
int n, m, si, sj, gi, gj;
string s[mxN];
bool e(int x, int y){
  return (x < n && x >= 0 && y < m && y >= 0);
}
 
void bfs(){
  queue<pair<pi, string> > fringe;
  fringe.push(make_pair(make_pair(si, sj), ""));
  s[si][sj] = '#';
  // vector<vi> count(n, vector<int>(m));
  while(!fringe.empty()){
    pair<pi, string> node = fringe.front();
    fringe.pop();
    pi pos = node.f;
    string path = node.s;
    // ++count[pos.f][pos.s];
    if(pos.f == gi && pos.s == gj){
      cout << "YES\n" << path.length() << "\n" << path << "\n";
      // for(int i = 0; i < n; i++){
      //   for(int j = 0; j < m; j++) cout << count[i][j];
      //   cout << "\n";
      // }
      return;
    }
    F0R(i, 4){
      int nx = pos.f + dx[i];
      int ny = pos.s + dy[i];
      if(!e(nx, ny)) continue;
      if(s[nx][ny] != '#'){
        s[nx][ny] = '#';
        fringe.push(make_pair( make_pair(nx, ny), path + ds[i]));
      }
    }
  }
  cout << "NO" << "\n";
  // for(int i = 0; i < n; i++){
  //   for(int j = 0; j < m; j++) cout << count[i][j];
  //   cout << "\n";
  // }
}
 
int main() {
  // freopen("input.txt", "r", stdin);
  ios:: sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  F0R(i, n){
    cin >> s[i];
    F0R(j, m){
      if (s[i][j] == 'A') si = i, sj = j;
      if (s[i][j] == 'B') gi = i, gj = j;
    }
  }
 
  bfs();
  return 0;
}

My second approach was to backtrack by storing the direction along the path. This also has TLE on test case 13.

#include <bits/stdc++.h>
 
using namespace std;
 
 
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
 
template <typename T> void setmax(T& a, const T& b) { if (b > a) a = b; }
 
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define F0R(i, a) for(ll i = 0; i < a; i++)
#define f first
#define s second
#define pb push_back
#define sz(a) int((a).size())
 
 
const int MOD = 1e9+7; // 998244353;
const int MX = 1000; //
const ll INF = 1e18; //
string ds = "RLUD";
int di[] = {0, 0, -1, 1};
int dj[] = {1, -1, 0, 0};
 
string maze[MX];
int n, m, si, sj, gi, gj, path[MX][MX];
 
 
 
bool o(int x, int y){
  return (x < 0 || x >= n || y < 0 || y >= m);
}
 
struct node{
  int i, j;
};
 
node init(int i, int j){
  return {i, j};
}
 
void bfs(){
  queue<node> q;
  q.push(init(si, sj));
  maze[si][sj] = '#';
  while(!q.empty()){
    node nn = q.front();
    q.pop();
    if(nn.i == gi && nn.j == gj){
      cout << "YES\n";
      int i = nn.i, j = nn.j;
      string out = "";
      while(i != si || j != sj){
        int k = path[i][j];
        out = ds[k] + out;
        i-= di[k];
        j-= dj[k];
      }
      cout << sz(out) << "\n" << out << "\n";
      return;
    }
    for(int k = 0; k < 4; k++){
      int ni = nn.i + di[k];
      int nj = nn.j + dj[k];
      if(!o(ni, nj) && maze[ni][nj] != '#'){
        maze[ni][nj] = '#';
        q.push(init(ni, nj));
        path[ni][nj] = k;
      }
    }
  }
  cout << "NO" << "\n";
}
 
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0); // see Fast Input & Output
  cin >> n >> m;
  F0R(i, n){
    cin >> maze[i];
    F0R(j, m){
      if (maze[i][j] == 'A') si = i, sj = j;
      else if (maze[i][j] == 'B') gi = i, gj = j;
    }
  }
  bfs();
}

I'm lost at this point. What else can I do to optimize in this problem?