fork download
copy 
  1. // SIGMA BOY hihihihihihihi
  2.  
  3. #define se second
  4. #define fi first
  5. #define pb push_back
  6. #define pob pop_back
  7. #define bitebi __builtin_popcountll
  8. #include <bits/stdc++.h>
  9.  
  10. using namespace std ;
  11. typedef long long ll;
  12. typedef long double ld;
  13. typedef pair<ll,ll> pll;
  14. typedef pair<int,int> pii;
  15. const ll Mod = 1e9+7;
  16. const ll Maxn = 1e3+1;
  17. const int oo = 1e9;
  18.  
  19. int moveJ[4] = {1,-1,0,0};
  20. int moveI[4] = {0,0,-1,1};
  21. char Direction[4] = {'R','L','U','D'};
  22. int moveJinverse[4] = {-1,1,0,0};
  23. int moveIinverse[4] = {0,0,1,-1};
  24.  
  25. int n , m , d_monster[Maxn][Maxn], d_A[Maxn][Maxn],a,b,x,y;
  26. pii flag = {0,0};
  27. queue<pii> monster, A;
  28. char c[Maxn][Maxn], tv[Maxn][Maxn];
  29.  
  30. void bfs ( queue<pii>&q , int tt)
  31. {
  32.     while(!q.empty())
  33.     {
  34.         auto id = q.front();
  35.         a = id.fi;
  36.         b = id.se;
  37.         if(tt&&(a==n||a==1||b==m||b==1))
  38.         {
  39.             flag = {a,b};
  40.             return;
  41.         }
  42.         q.pop();
  43.         for (int i = 0 ; i < 4 ; ++i)
  44.         {
  45.             x = a+moveI[i];
  46.             y = b+moveJ[i];
  47.             if(c[x][y]=='#') continue;
  48.             if(!tt&&d_monster[x][y]==oo)
  49.             {
  50.                 //cout << x << ' ' << y << ' ' << d_monster[x][y] << '\n';
  51.                 d_monster[x][y]=d_monster[a][b]+1;
  52.                 q.push({x,y});
  53.             }
  54.  
  55.             if(tt && d_A[x][y] == -1)
  56.             {
  57.                 d_A[x][y] = d_A[a][b]+1;
  58.                 if(d_A[x][y] < d_monster[x][y])
  59.                 {
  60.                     tv[x][y] = Direction[i];
  61.                     q.push({x,y});
  62.                 }
  63.             }
  64.         }
  65.     }
  66. }
  67.  
  68. void Do()
  69. {
  70.     cin >> n >> m ;
  71.     for (int i = 1 ; i <= n ; ++i)
  72.     {
  73.         fill(d_monster[i]+1,d_monster[i]+m+1,oo);
  74.         fill(d_A[i]+1,d_A[i]+m+1,-1);
  75.     }
  76.  
  77.     for (int i = 1 ; i <= n ; ++i)
  78.     {
  79.         for (int j = 1 ; j <= m ; ++j)
  80.         {
  81.             cin >> c[i][j];
  82.             if(c[i][j]=='M')
  83.             {
  84.                 monster.push({i,j});
  85.                 d_monster[i][j] = 0;
  86.             }
  87.             else if(c[i][j]=='A')
  88.             {
  89.                 A.push({i,j});
  90.                 d_A[i][j] = 0;
  91.             }
  92.         }
  93.     }
  94.  
  95.     bfs(monster,0);
  96.     bfs(A,1);
  97.     if(flag.fi==0)
  98.     {
  99.         cout << "NO\n";
  100.         return;
  101.     }
  102.     cout << "YES\n";
  103.     vector<char> res;
  104.     x = flag.fi;
  105.     y = flag.se;
  106.     while(c[x][y]!='A')
  107.     {
  108.         for (int i = 0 ; i < 4 ; ++i)
  109.         {
  110.             if(Direction[i]==tv[x][y])
  111.             {
  112.                 res.pb(tv[x][y]);
  113.                 x += moveIinverse[i];
  114.                 y += moveJinverse[i];
  115.                 break;
  116.             }
  117.         }
  118.     }
  119.     reverse(res.begin(),res.end());
  120.     cout << res.size() << '\n' ;
  121.     for (auto x:res)
  122.         cout << x;
  123. }
  124.  
  125. signed main ()
  126. {
  127.     ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  128. #define task "test"
  129.     if(fopen(task".inp", "r")){
  130.         freopen(task".inp", "r", stdin);
  131.         freopen(task".out", "w", stdout);
  132.     }
  133.     int ntest=1;
  134.     while(ntest--) Do();
  135.  
  136.     cerr<<"\nTime elapsed: "<<1000*clock()/CLOCKS_PER_SEC<<"ms\n";
  137. }
  138.  
Success #stdin #stdout #stderr 0.01s 5652KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
NO
stderr
copy 
Time elapsed: 4ms
https://ideone.com/MKtiI9
language:
C++14 (gcc 8.3)
created:
13 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!