// compile: g++ -o data data.cpp -std=gnu++20 -DLOCAL -g
// run: ./data < data.in
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#ifdef LOCAL
#endif
#define sz(v) ((int)(v).size())
#define PV(v) for (int i=0;i<v.size();++i)cout<<v[i]<<" ";cout<<endl;
#define OK cout<<"OK"<<endl;
#define INTINF 9223372036854775807
#define int long long
#define MAXN 1010
using namespace std;
int n = 0, s, d;
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int f[MAXN][MAXN];
int pre[MAXN*MAXN];
vector<int> e[MAXN*MAXN];
pair<int, int> coor[MAXN*MAXN];
struct node {
int x, dis;
};
vector<node> q;
int bfs(int s, int d) {
vector<int> vis(n, 0); vis[s] = 1;
int head = 0, tail = -1;
++tail; q.push_back({s, 0});
while (head <= tail) {
node u = q[head++];
// for (auto v = e[u.x].begin(); v != e[u.x].end(); ++v) {
for (auto v = e[u.x].begin(); v != e[u.x].end(); ++v) {
if (vis[*v]) continue;
++tail; q.push_back({*v, u.dis + 1});
vis[*v] = 1;
pre[tail] = head - 1;
if (*v == d) return tail;
}
}
return -1;
}
char direction(int u, int v) {
pair<int, int> x = coor[u];
pair<int, int> y = coor[v];
int d = -1;
for (int i = 0; i < 4; ++i) {
if (x.first + dir[i][0] == y.first && x.second + dir[i][1] == y.second) {
d = i;
break;
}
}
if (d == 0) return 'R';
else if (d == 1) return 'D';
else if (d == 2) return 'L';
else if (d == 3) return 'U';
else return '!';
}
void travesal(int last) {
cout << q[last].dis << endl;
vector<int> a;
for (int i = last; ~i; i = pre[i]) a.push_back(q[i].x);
reverse(a.begin(), a.end());
for (int i = 0; i < sz(a)-1; ++i) cout << direction(a[i], a[i+1]);
cout << endl;
}
int32_t main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
memset(f, -1, sizeof(f));
memset(pre, -1, sizeof(pre));
int mapn, mapm; cin >> mapn >> mapm;
for (int i = 0; i < mapn; ++i) {
string str; cin >> str;
for (int j = 0; j < str.length(); ++j) {
if (str[j] == 'A') s = n, coor[n] = make_pair(i, j), f[i+1][j+1] = n++;
else if (str[j] == 'B') d = n, coor[n] = make_pair(i, j), f[i+1][j+1] = n++;
else if (str[j] == '.') coor[n] = make_pair(i, j), f[i+1][j+1] = n++;
}
}
for (int i = 1; i <= mapn; ++i) {
for (int j = 1; j <= mapm; ++j) {
if (!~f[i][j]) continue;
for (int k = 0; k < 4; ++k) {
if (~f[i + dir[k][0]][j + dir[k][1]]) e[f[i][j]].push_back(f[i + dir[k][0]][j + dir[k][1]]);
}
}
}
// for (int i = 1; i <= mapn; ++i) {
// for (int j = 1; j <= mapm; ++j) {
// cout << f[i][j] << "\t";
// }
// cout << endl;
// }
// for (int i = 0; i < n; ++i) {
// cout << i << ":\t";
// for (auto it = e[i].begin(); it != e[i].end(); ++it) {
// cout << (*it) << "\t";
// }
// cout << endl;
// }
// return 0;
int last = bfs(s, d);
if (~last) {
cout << "YES" << endl;
travesal(last);
}
else cout << "NO" << endl;
return 0;
}
No Comments