Untitled
unknown
plain_text
a year ago
2.1 kB
16
Indexable
#include <bits/stdc++.h>
using namespace std;
void File() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
#ifdef MON
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("errors.txt", "w", stderr);
#else
#endif
}
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
char di[] = {'D', 'U', 'R', 'L'};
int main() {
File();
int n, m;
cin >> n >> m;
char a[n][m];
queue<pair<int, int>> q;
vector<vector<bool>> vis(n, vector<bool>(m, false));
vector<vector<int>> par(n, vector<int>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> a[i][j];
if (a[i][j] == 'A') {
q.push({i, j});
vis[i][j] = true;
par[i][j] = -1;
}
}
}
while (!q.empty()) {
int i = q.front().first, j = q.front().second;
q.pop();
for (int k = 0; k < 4; ++k) {
int ni = i + dx[k], nj = j + dy[k];
if (ni >= 0 && ni < n && nj >= 0 && nj < m && a[ni][nj] != '#' && !vis[ni][nj]) {
q.push({ni, nj});
par[ni][nj] = k;
vis[ni][nj] = true;
}
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (a[i][j] == 'B') {
if (vis[i][j]) {
cout << "YES\n";
vector<char> path;
int x = i, y = j;
while (par[x][y] != -1) {
int k = par[x][y];
x = x - dx[k], y = y - dy[k];
path.push_back(di[k]);
}
cout << path.size() << "\n";
reverse(path.begin(), path.end());
for (auto &c: path) cout << c;
} else {
cout << "NO\n";
}
}
}
}
return 0;
}Editor is loading...
Leave a Comment