fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FIO ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
  3. #define ll long long
  4. #define ull unsigned long long
  5. #define ld long double
  6. #define Yes cout << "YES\n"
  7. #define No  cout << "NO\n"
  8. using namespace std;
  9. // #define IO freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
  10. constexpr  int MX = 2e5 + 5;
  11. constexpr int MOD = 1e9 + 7;
  12. #define all(v) v.begin() , v.end()
  13. #define rall(v) v.rbegin() , v.rend()
  14. #define pb push_back
  15. #define MP make_pair
  16. #define nl '\n'
  17.  
  18. char grid[1005][1005];
  19. bool vis[1005][1005];
  20. queue<pair<int,int>> q;
  21. pair<int , int> p[1005][1005];
  22.  
  23. vector<vector<int>> directions = {
  24.     {1 , 0} , {-1 , 0} , {0 , 1} , {0 , -1}
  25. };
  26.  
  27. void solve()
  28. {
  29.     int n , m;
  30.     cin >> n >> m;
  31.     int x1 = 0 , y1 = 0 , x2 = -1 , y2 = -1;
  32.     for (int i = 1 ; i <= n ; i++) {
  33.         for (int j = 1; j <= m ; j++) {
  34.             cin >> grid[i][j];
  35.             if (grid[i][j] == 'A') x1 = i , y1 = j;
  36.             else if (grid[i][j] == 'M') q.emplace(i , j);
  37.         }
  38.     }
  39.     bool good = false;
  40.     p[x1][y1] = MP(-1 , -1); vis[x1][y1] = true; q.emplace(x1 , y1);
  41.     while (!q.empty()) {
  42.         auto&[a , b] = q.front(); q.pop();
  43.         if (grid[a][b] != 'M' and (a == 1 or a == n or b == 1 or b == m)) {
  44.             x2 = a , y2 = b;
  45.             good = true;
  46.             break;
  47.         }
  48.         for (auto& d : directions) {
  49.             int nx = a + d[0] , ny = b + d[1];
  50.             bool valid = nx >= 1 && nx <= n && ny >= 1 && ny <= m && grid[nx][ny] == '.';
  51.             if (valid) {
  52.                 grid[nx][ny] = grid[a][b];
  53.                 p[nx][ny] = MP(a , b);
  54.                 q.emplace(nx , ny);
  55.             }
  56.         }
  57.     }
  58.     if(!good) {
  59.         cout << "NO";
  60.         return;
  61.     }
  62.     vector<char> ans;
  63.     while (p[x2][y2] != MP(-1 , -1)) {
  64.         auto&[px , py] = p[x2][y2];
  65.         if (px == x2 + 1) ans.pb('U');
  66.         if (px == x2 - 1) ans.pb('D');
  67.         if (py == y2 + 1) ans.pb('L');
  68.         if (py == y2 - 1) ans.pb('R');
  69.         x2 = px , y2 = py;
  70.     }
  71.     reverse(all(ans));
  72.     cout << "YES" << nl;
  73.     cout << ans.size() << nl;
  74.     for (const auto& c : ans) cout << c;
  75. }
  76.  
  77. int main()
  78. {
  79.     FIO
  80. // #ifndef ONLINE_JUDGE
  81. // IO
  82. // #endif
  83.     int tt = 1;
  84.     // cin >> tt;
  85.     while (tt--) {
  86.         solve();
  87.     }
  88.     return 0;
  89. }
Success #stdin #stdout 0.01s 5584KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
YES
0
https://ideone.com/7KBKs5
language:
C++14 (gcc 8.3)
created:
5 hours 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!