fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define endl "\n"
  3. using namespace std;
  4. #define int long long int
  5.  
  6. int n, m;
  7. vector<pair<int,int>> monster;
  8. vector<vector<int>> g;
  9. map<pair<int,int>, pair<int,int>> par_mp;
  10. pair<int,int> si, se; 
  11. vector<pair<int,int>> moves = {{-1,0},{1,0},{0,1},{0,-1}}; 
  12.  
  13. bool isValid(int x, int y, int timer)
  14. {
  15.   if(x<0 or y<0 or x>=n or y>=m)
  16.   {
  17.     return false;
  18.   }
  19.   if(g[x][y] <= timer)
  20.   {
  21.     return false;
  22.   }
  23.   return true;
  24. }
  25.  
  26. bool isExcape(int x, int y, int timer)
  27. {
  28.   if(!isValid(x,y,timer)) return false;
  29.   if(x == 0 or y == 0 or 
  30.     x == n-1 or y == m-1) return true;
  31.   return false;
  32. }
  33.  
  34. bool bfs_escape()
  35. {
  36.   queue<pair<pair<int,int>,int>> q;
  37.   q.push(make_pair(si,0));
  38.   par_mp[si] = {-1,-1};
  39.   while(!q.empty())
  40.   {
  41.     int cx = q.front().first.first;
  42.     int cy = q.front().first.second;
  43.     int timer = q.front().second; 
  44.     timer++; q.pop();
  45.     for(auto mv: moves)
  46.     {
  47.       int tx = cx+mv.first;
  48.       int ty = cy+mv.second;
  49.       if(isExcape(tx,ty,timer))
  50.       {
  51.        par_mp[{tx,ty}] = {cx,cy};
  52.        se = {tx,ty}; return true; 
  53.       }
  54.       if(isValid(tx,ty,timer))
  55.       {
  56.         par_mp[{tx,ty}] = {cx,cy};
  57.         g[tx][ty] = timer;
  58.         q.push({{tx,ty},timer});
  59.       }
  60.     }
  61.   }
  62.   return false;
  63. }
  64.  
  65. void preprocess_lava_flow()
  66. {
  67.   queue<pair<pair<int,int>,int>> q;
  68.   for(auto m: monster)
  69.   {
  70.     q.push(make_pair(m,0));
  71.   }
  72.   while(!q.empty())
  73.   {
  74.     int cx = q.front().first.first;
  75.     int cy = q.front().first.second;
  76.     int timer = q.front().second; 
  77.     timer++; q.pop();
  78.  
  79.     for(auto mv: moves)
  80.     {
  81.       int tx = cx+mv.first;
  82.       int ty = cy+mv.second;
  83.       if(isValid(tx,ty,timer))
  84.       {
  85.         g[tx][ty] = timer;
  86.         q.push({{tx,ty},timer});
  87.       }
  88.     }
  89.   }
  90.  
  91.  
  92.  
  93. }
  94.  
  95. int32_t main()
  96. {
  97.   ios_base::sync_with_stdio(false);
  98.   cin.tie(NULL);
  99.   cin >> n >> m;
  100.   g.resize(n);
  101.   for(int i = 0; i < n; ++i)
  102.   {
  103.     g[i].resize(m);
  104.   }
  105.  
  106.   for(int i = 0; i < n; ++i)
  107.   {
  108.     for (int j = 0; j < m; ++j)
  109.     {
  110.       g[i][j] = INT_MAX;
  111.     }
  112.   }  
  113.  
  114.   for(int i = 0; i < n; ++i)
  115.   {
  116.     for (int j = 0; j < m; ++j)
  117.     {
  118.       char c; cin >> c;
  119.       if(c == '#')
  120.       {
  121.         g[i][j] = 0;
  122.       }
  123.       else if(c == 'M')
  124.       {
  125.         g[i][j] = 0;
  126.  
  127.           monster.push_back({i,j});
  128.       }
  129.       else if(c == 'A')
  130.       {
  131.         g[i][j] = 0;
  132.         si = {i,j};
  133.       }
  134.       else
  135.       {
  136.         g[i][j] = INT_MAX;
  137.       }
  138.     }
  139.   }
  140.   if(si.first == 0 or si.second == 0 or si.first == n-1 or si.second == m-1) 
  141.   {
  142.     cout << "YES" << endl;
  143.     cout << 0;
  144.     return 0;
  145.   }
  146.   preprocess_lava_flow();
  147.  
  148.   if(!bfs_escape())
  149.   {
  150.     cout << "NO";
  151.     return 0;
  152.   }
  153.   cout << "YES" << endl;
  154.   pair<int,int> tmp = se;
  155.   pair<int,int> tmp1 = par_mp[se];
  156.   pair<int,int> ed = {-1,-1}; 
  157.   vector<char> ans;
  158.   while(tmp1 != ed)
  159.   {
  160.  
  161.     if((tmp.second - tmp1.second) == 1 and (tmp.first - tmp1.first) == 0)
  162.     {
  163.       ans.push_back('R');
  164.     }
  165.     if((tmp.second - tmp1.second) == -1 and (tmp.first - tmp1.first) == 0)
  166.     {
  167.       ans.push_back('L');
  168.     }
  169.     if((tmp.second - tmp1.second) == 0 and (tmp.first - tmp1.first) == 1)
  170.     {
  171.       ans.push_back('D');
  172.     }
  173.     if((tmp.second - tmp1.second) == 0 and (tmp.first - tmp1.first) == -1)
  174.     {
  175.       ans.push_back('U');
  176.     }
  177.     tmp = par_mp[tmp];
  178.     tmp1 = par_mp[tmp];
  179.   }
  180.   reverse(ans.begin(), ans.end());
  181.   cout << ans.size() << endl;
  182.   for(auto c: ans)
  183.   {
  184.     cout << c;
  185.   }
  186. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
YES
0
https://ideone.com/PGxnxd
language:
C++14 (gcc 8.3)
created:
8 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!