Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 1003;
- int n, m;
- int vis[N][N], d[N][N];
- char c[N][N];
- int main(){
- memset(d, -1, sizeof(d));
- cin >> n >> m;
- pair <int, int> Begin, End;
- for (int i = 1; i <= n; i++) {
- for (int j = 1; j <= m; j++) {
- cin >> c[i][j];
- if (c[i][j] == 'A') {
- Begin = make_pair(i, j);
- }
- if (c[i][j] == 'B') {
- End = make_pair(i, j);
- }
- }
- }
- queue < pair <int, int> > q;
- vis[Begin.first][Begin.second] = 1;
- d[Begin.first][Begin.second] = 0;
- q.push(Begin);
- while (!q.empty()) {
- pair <int, int> v = q.front();
- int x = v.first, y = v.second;
- q.pop();
- if ((c[x - 1][y] == '.' || c[x - 1][y] == 'B') && vis[x - 1][y] == 0) {
- vis[x - 1][y] = 1;
- d[x - 1][y] = d[x][y] + 1;
- q.push({x - 1, y});
- }
- if ((c[x + 1][y] == '.' || c[x + 1][y] == 'B') && vis[x + 1][y] == 0) {
- vis[x + 1][y] = 1;
- d[x + 1][y] = d[x][y] + 1;
- q.push({x + 1, y});
- }
- if ((c[x][y - 1] == '.' || c[x][y - 1] == 'B') && vis[x][y - 1] == 0) {
- vis[x][y - 1] = 1;
- d[x][y - 1] = d[x][y] + 1;
- q.push({x, y - 1});
- }
- if ((c[x][y + 1] == '.' || c[x][y + 1] == 'B') && vis[x][y + 1] == 0) {
- vis[x][y + 1] = 1;
- d[x][y + 1] = d[x][y] + 1;
- q.push({x, y + 1});
- }
- }
- if (vis[End.first][End.second] == 0) {
- cout << "NO\n";
- return 0;
- }
- cout << "YES\n";
- cout << d[End.first][End.second] << endl;
- string path;
- while (End != Begin) {
- if (d[End.first][End.second] - 1 == d[End.first - 1][End.second]) {
- End.first--;
- path += 'D';
- continue;
- }
- if (d[End.first][End.second] - 1 == d[End.first + 1][End.second]) {
- End.first++;
- path += 'U';
- continue;
- }
- if (d[End.first][End.second] - 1 == d[End.first][End.second - 1]) {
- End.second--;
- path += 'R';
- continue;
- }
- if (d[End.first][End.second] - 1 == d[End.first][End.second + 1]) {
- End.second++;
- path += 'L';
- continue;
- }
- }
- reverse(path.begin(), path.end());
- cout << path << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement