fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. typedef long long ll;
  4.  
  5. #define fi first
  6. #define se second
  7. #define pii pair<ll, ll>
  8.  
  9. using namespace std;
  10. const int N = 1e3 + 5;
  11.  
  12. ll n, m, stx, sty;
  13. char a[N][N];
  14. ll vis[N][N], vism[N][N];
  15. ll tx[] = {-1, 0, 0, 1};
  16. ll ty[] = {0, -1, 1, 0};
  17. ll ai[N][N], aj[N][N];
  18. bool ok = false;
  19. queue <pii> mq;
  20.  
  21. bool inside(ll u, ll v) {
  22.     return (u > 0 && u <= n && v > 0 && v <= m);
  23. }
  24.  
  25. void bfs(ll s1, ll s2) {
  26.     queue <pii> q;
  27.     q.push({s1, s2});
  28.     vis[s1][s2] = 1;
  29.     while (!q.empty()) {
  30.         ll m = mq.size();
  31.         while (m--) {
  32.             ll mx = mq.front().fi;
  33.             ll my = mq.front().se;
  34.             mq.pop();
  35.             for (int i = 0; i < 4; i++) {
  36.                 ll mu = mx + tx[i];
  37.                 ll mv = my + ty[i];
  38.                 if (!inside(mu, mv) || a[mu][mv] == '#'|| vism[mu][mv])
  39.                     continue;
  40.                 vism[mu][mv] = vism[mx][my] + 1;
  41.                 mq.push({mu, mv});
  42.             }
  43.         }
  44.  
  45.         ll x = q.front().fi;
  46.         ll y = q.front().se;
  47.         q.pop();
  48.         for (int i = 0; i < 4; i++) {
  49.             ll u = x + tx[i];
  50.             ll v = y + ty[i];
  51.             if (!inside(u, v) || a[u][v] == '#' || vis[u][v] || (vism[u][v] && vism[u][v] <= vis[x][y] + 1))
  52.                 continue;
  53.             ai[u][v] = x;
  54.             aj[u][v] = y;
  55.             q.push({u, v});
  56.             vis[u][v] = vis[x][y] + 1;
  57.         }
  58.     }
  59. }
  60.  
  61. int main() {
  62.     ios_base::sync_with_stdio(false);
  63.     cin.tie(0);
  64.     cout.tie(0);
  65.     // freopen("in.inp", "r", stdin);
  66.     // freopen("ou.out", "w", stdout);
  67.  
  68.     cin >> n >> m;
  69.     for (int i = 1; i <= n; i++) {
  70.         for (int j = 1; j <= m; j++) {
  71.             cin >> a[i][j];
  72.         }
  73.     }
  74.  
  75.     vector <pii> ans;
  76.     for (int i = 1; i <= n; i++) {
  77.         for (int j = 1; j <= m; j++) {
  78.             if (a[i][j] == 'A') {
  79.                 if (i == n || j == m || i == 1 || j == 1) {
  80.                     cout << "YES\n";
  81.                     cout <<"0";
  82.                     return 0;
  83.                 }
  84.                 stx = i;
  85.                 sty = j;
  86.             }
  87.             if (a[i][j] == 'M') {
  88.                 mq.push({i, j});
  89.                 vism[i][j] = 1;
  90.             }
  91.             if ((i == n || j == m || i == 1 || j == 1) && a[i][j] == '.') {
  92.                 ans.push_back({i, j});
  93.             }
  94.         }
  95.     }
  96.  
  97.     if (ans.empty()) {
  98.         cout << "NO";
  99.         return 0;
  100.     }
  101.  
  102.     bfs(stx, sty);
  103.  
  104.     stack <char> res;
  105.     for (auto it : ans) {
  106.         if (vis[it.fi][it.se] == 0)
  107.             continue;
  108.         ll x = it.fi, y = it.se;
  109.         while (x != stx || y != sty) {
  110.             ll dx = ai[x][y];
  111.             ll dy = aj[x][y];
  112.             if (dx == x - 1)
  113.                 res.push('D');
  114.             else if (dx == x + 1)
  115.                 res.push('U');
  116.             else if (dy == y - 1)
  117.                 res.push('R');
  118.             else if (dy == y + 1)
  119.                 res.push('L');
  120.             x = dx;
  121.             y = dy;
  122.         }
  123.  
  124.         if (res.size() <= n * m) {
  125.             cout << "YES" << "\n" << res.size() << "\n";
  126.             while (!res.empty()) {
  127.                 cout << res.top();
  128.                 res.pop();
  129.             }
  130.             return 0;
  131.         }
  132.         else res = stack <char> ();
  133.     }
  134.  
  135.     cout << "NO";
  136.     return 0;
  137. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
NO
https://ideone.com/jFoS1q
language:
C++ (gcc 8.3)
created:
7 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!