fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define arwa ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  5. const int N = 1005;
  6. vector<int> adj[N];
  7. char a[N][N];
  8. int n, m;
  9. int dx[] = {0, 0, 1, -1};
  10. int dy[] = {1, -1, 0, 0};
  11.  
  12. bool valid(int x, int y) {
  13.     return (x >= 0 && x < n && y >= 0 && y < m && a[x][y] != '#');
  14. }
  15.  
  16. string bfs(int sx, int sy, int ex, int ey) {
  17.     queue<pair<int, int>> q;
  18.     q.push({sx, sy});
  19.     map<pair<int, int>, pair<int, int>> parents;
  20.     parents[q.front()] = {-1, -1};
  21.     bool isThereAPath = false;
  22.  
  23.     while (!q.empty()) {
  24.         pair<int, int> p = q.front();
  25.         int X = p.first, Y = p.second;
  26.         q.pop();
  27.  
  28.         if (X == ex && Y == ey) {
  29.             isThereAPath = true;
  30.             break;
  31.         }
  32.  
  33.         for (int i = 0; i < 4; i++) {
  34.             int nx = X + dx[i], ny = Y + dy[i];
  35.             if (valid(nx, ny) && parents.find({nx, ny}) == parents.end()) {
  36.                 parents[{nx, ny}] = {X, Y};
  37.                 q.push({nx, ny});
  38.             }
  39.         }
  40.     }
  41.  
  42.     vector<pair<int, int>> path;
  43.     if (isThereAPath) {
  44.         pair<int, int> current = {ex, ey};
  45.         while (current != make_pair(-1, -1)) {
  46.             path.push_back(current);
  47.             current = parents[current];
  48.         }
  49.         reverse(path.begin(), path.end());
  50.         string pathChar = "";
  51.         pair<int, int> prevPoint = {sx, sy};
  52.         for (int i = 1; i < path.size(); i++) {
  53.             if (path[i].first < prevPoint.first)
  54.                 pathChar += 'U';
  55.             else if (path[i].first > prevPoint.first)
  56.                 pathChar += 'D';
  57.             else if (path[i].second < prevPoint.second)
  58.                 pathChar += 'L';
  59.             else if (path[i].second > prevPoint.second)
  60.                 pathChar += 'R';
  61.  
  62.             prevPoint = path[i];
  63.         }
  64.         return pathChar;
  65.     }
  66.     return "";
  67. }
  68.  
  69. void solve() {
  70.     cin >> n >> m;
  71.     int sx, sy, ex, ey;
  72.     for (int i = 0; i < n; i++) {
  73.         for (int j = 0; j < m; j++) {
  74.             cin >> a[i][j];
  75.             if (a[i][j] == 'A') {
  76.                 sx = i, sy = j;
  77.             }
  78.             if (a[i][j] == 'B') {
  79.                 ex = i;
  80.                 ey = j;
  81.             }
  82.         }
  83.     }
  84.     string ans = bfs(sx, sy, ex, ey);
  85.     if (ans.empty()) {
  86.         cout << "NO\n";
  87.         return;
  88.     }
  89.     cout << "YES\n" << ans.size() << "\n" << ans << "\n";
  90. }
  91.  
  92. int main() {
  93.     arwa
  94.     int t = 1;
  95.     // cin >> t;
  96.     while (t--) {
  97.         solve();
  98.     }
  99. }
  100.  
Success #stdin #stdout 0.01s 5264KB
comments (?)
stdin 
Standard input is empty
stdout 
NO
https://ideone.com/ClJm6J
language:
C++ (gcc 8.3)
created:
24 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!