fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define max3(a, b, c) max(a, max(b, c))
  5. #define writef(a, n) cout << fixed << setprecision(n) << a
  6. using namespace std;
  7. typedef long double ld;
  8. typedef long long ll;
  9. typedef unsigned long long ull;
  10. typedef pair<ll, ll> ii;
  11. typedef pair<ll, ii> iii;
  12. typedef vector<ll> vi;
  13. typedef vector<ii> vii;
  14. typedef vector<iii> viii;
  15.  
  16. int main() {
  17.     ios::sync_with_stdio(0);
  18.     cin.tie(0);
  19.  
  20.     ii start, end;
  21.     ll n, m;
  22.     string res = "";
  23.     char a[1000][1000];
  24.     int previoustep[1000][1000];
  25.     string stepdir = " URDL";
  26.     ll dx[5] = {100, -1, 0, 1, 0};
  27.     ll dy[5] = {100, 0, 1, 0, -1};
  28.  
  29.     cin >> n >> m;
  30.  
  31.     for (int i = 0; i < n; i++)
  32.         for (int j = 0; j < m; j++) {
  33.             cin >> a[i][j];
  34.             if (a[i][j] == 'A') {
  35.                 start.fi = i;
  36.                 start.se = j;
  37.             } else if (a[i][j] == 'B') {
  38.                 end.fi = i;
  39.                 end.se = j;
  40.             }
  41.             previoustep[i][j] = 0;
  42.         }
  43.  
  44.     queue<ii> q;
  45.     q.push(start);
  46.  
  47.     while (!q.empty()) {
  48.         ii pos = q.front();
  49.         q.pop();
  50.  
  51.         for (int i = 1; i <= 4; i++) {
  52.             ii temp = {pos.fi + dx[i], pos.se + dy[i]};
  53.  
  54.             if (temp.fi >= n || temp.se >= m || temp.fi < 0 || temp.se < 0 ||
  55.                 a[temp.fi][temp.se] == '#' || previoustep[temp.fi][temp.se])
  56.                 continue;
  57.             previoustep[temp.fi][temp.se] = i;
  58.             if (a[temp.fi][temp.se] != 'B') q.push(temp);
  59.         }
  60.     }
  61.  
  62.     if (previoustep[end.fi][end.se]) {
  63.         cout << "YES\n";
  64.         ll num = 0;
  65.         while (end != start) {
  66.             num++;
  67.             ll temp = previoustep[end.fi][end.se];
  68.             res += stepdir[temp];
  69.             end.fi -= dx[temp];
  70.             end.se -= dy[temp];
  71.         }
  72.         reverse(res.begin(), res.end());
  73.         cout << num << "\n" << res << "\n";
  74.     } else
  75.         cout << "NO\n";
  76. }
Success #stdin #stdout 0.01s 5456KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
NO
https://ideone.com/XnYN2A
language:
C++14 (clang 8.0)
created:
2 years 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!