CCCPaste

Untitled

#include <iostream>
#include <queue>

#include <bits/stdc++.h>
using namespace std;
char mat[1111][1111];
bool visited[1111][1111];
int prev_steps[1111][1111];
int main() {
ios_base::sync_with_stdio(false);

int n, m;
cin >> n >> m;
int si, sj, ei, ej;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cin >> mat[i][j];
visited[i][j] = false;
if(mat[i][j] == 'A') {
si = i; sj = j;
}
if(mat[i][j] == 'B') {
ei = i; ej = j;
}
}
}
int di[] = {1, -1, 0, 0};
int dj[] = {0, 0, 1, -1};
queue<int> Q;
Q.push(si); Q.push(sj); Q.push(0);
visited[si][sj] = true;
int dist = -1;
while(!Q.empty()) {
int ci = Q.front(); Q.pop();
int cj = Q.front(); Q.pop();
int cekor = Q.front(); Q.pop();

if(ci == ei and cj == ej) {
dist = cekor;
break;
}
for(int i = 0; i < 4; i++) {
int ti = ci + di[i];
int tj = cj + dj[i];
if(ti >= 0 and ti < n and tj >= 0 and tj < m and !visited[ti][tj] and mat[ti][tj] != '#') {
Q.push(ti);
Q.push(tj);
Q.push(cekor + 1);
visited[ti][tj] = true;
prev_steps[ti][tj] = i;
}
}
}
if(dist == -1) {
cout << "NO" << endl;
return 0;
}
cout << "YES" << endl << dist << endl;
pair<int, int> S = make_pair(si, sj), E = make_pair(ei, ej);
string result = "";
while(E != S) {
int dir = prev_steps[E.first][E.second];
if(dir == 0) {
result += "D";
}
else if(dir == 1) {
result += "U";
}
else if(dir == 2) {
result += "R";
}
else {
result += "L";
}
E = make_pair(E.first - di[dir], E.second - dj[dir]);
}
reverse(result.begin(), result.end());
cout << result << endl;
return 0;
}