fork(2) download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long int
  5. #define vi vector<int>
  6. #define vvi vector<vi>
  7. #define read(a)  for(int i = 0; i < n; i++) cin >> a[i];
  8. #define print(a)  for(int i = 0; i < n; i++) cout << a[i] << " ";
  9. #define pb push_back
  10. #define pql priority_queue<int>
  11. #define pqs priority_queue<int, vi, greater<int>>
  12. #define pqlv priority_queue<vi>
  13. #define pqsv priority_queue<vi, vvi, greater<vi>>
  14. #define endl '\n'
  15. #define N 1234567
  16. #define MOD 1000000007
  17.  
  18. vector<string> v;
  19. int n, m;
  20.  
  21. int dist[101][101];
  22. int d[101][101];
  23.  
  24. signed main() {
  25.     ios::sync_with_stdio(false); 
  26.     cin.tie(0); 
  27.     cout.tie(0);
  28.     int t = 1;
  29.     // cin >> t;
  30.     while(t--) {
  31.         memset(dist, -1, sizeof dist);
  32.         cin >> n >> m;
  33.         v.clear();
  34.         v.resize(n);
  35.         for(int i = 0; i < n; i++) {
  36.             cin >> v[i];
  37.         }
  38.         int x, y, c1, c2;
  39.         queue<vi> q;
  40.         for(int i = 0; i < n; i++) {
  41.             for(int j = 0; j < m; j++) {
  42.                 if(v[i][j] == 'M') {
  43.                     q.push({ i, j, 0 });
  44.                 }
  45.                 if(v[i][j] == 'A') {
  46.                     x = i; y = j;
  47.                 }
  48.             }
  49.         }
  50.         c1 = x; c2 = y;
  51.         while(!q.empty()) {
  52.             auto f = q.front();
  53.             q.pop();
  54.             int x = f[0], y = f[1], steps = f[2];
  55.             if(x < 0 || x > n - 1 || y < 0 || y > m - 1 || v[x][y] == '#' || dist[x][y] != -1) {
  56.                 continue;
  57.             }
  58.             dist[x][y] = steps;
  59.             vi dx = { 0, 0, -1, 1 };
  60.             vi dy = { -1, 1, 0, 0 };
  61.             for(int i = 0; i < 4; i++) {
  62.                 int cx = x + dx[i], cy = y + dy[i];
  63.                 q.push({ cx, cy, steps + 1 });
  64.             }
  65.         }
  66.         int cnt = 0;
  67.         string ret;
  68.         while(!q.empty())   q.pop();
  69.         q.push({ x, y, 0, 0 });
  70.         memset(d, -1, sizeof d);
  71.         bool ans = false;
  72.         // L => 0, R => 1, U => 2, D => 3
  73.         int p[n + 1][m + 1];
  74.         memset(p, 0, sizeof p);
  75.         while(!q.empty()) {
  76.             auto f = q.front();
  77.             q.pop();
  78.             int x = f[0], y = f[1], steps = f[2], dir = f[3];
  79.             if(x < 0 || x > n - 1 || y < 0 || y > m - 1 || v[x][y] == '#' || d[x][y] != -1 || (dist[x][y] >= 0 && dist[x][y] <= steps))
  80.                 continue;
  81.             if(x == n - 1 || y == m - 1 || x == 0 || y == 0) {
  82.                 p[x][y] = dir;
  83.                 while(x != c1 || y != c2) {
  84.                     cnt++;
  85.                     if(p[x][y] == 0)    ret += 'L', y++;
  86.                     else if(p[x][y] == 1)   ret += 'R', y--;
  87.                     else if(p[x][y] == 2)   ret += 'U', x++;
  88.                     else    ret += 'D', x--;
  89.                 }
  90.                 ans = true;
  91.                 break;
  92.             }
  93.             d[x][y] = steps;
  94.             p[x][y] = dir;
  95.             vi dx = { 0, 0, -1, 1 };
  96.             vi dy = { -1, 1, 0, 0 };
  97.             for(int i = 0; i < 4; i++) {
  98.                 int cx = x + dx[i], cy = y + dy[i];
  99.                 q.push({ cx, cy, steps + 1, i });
  100.             }
  101.         }
  102.         if(ans) {
  103.             reverse(ret.begin(), ret.end());
  104.             cout << "YES" << endl << cnt << endl << ret;
  105.         }
  106.         else
  107.             cout << "NO";
  108.         cout << endl;
  109.     }
  110. 	return 0;
  111. }
Success #stdin #stdout 0s 4316KB
comments (?)
stdin 
5 8
########
#M..A..#
#.#.M#.#
#M#..#..
#.######
stdout 
YES
5
RRDDR
https://ideone.com/K7jEpR
language:
C++14 (gcc 8.3)
created:
4 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!