fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define pb push_back
  4. #define all(x) x.begin(), x.end()
  5. typedef long long ll;
  6. const ll INF = (ll)1e13;
  7. const ll MOD = 1000000007;
  8.  
  9. ll n , m;
  10. vector< vector < bool > > vis ;
  11. vector < vector < char > > parent ;
  12. vector < vector <ll > >monster,humain ;
  13. vector < vector < char > > matrix ;
  14. bool valid (ll i , ll j ) {
  15. return i >= 0 && i < n && j >= 0 && j < m && !vis[i][j] && matrix[i][j] == '.';
  16. }
  17.  
  18. void bfs(queue< pair < ll , ll > >& q , vector < vector < ll > >& v , bool test) {
  19. while (!q.empty()) {
  20. pair < ll , ll > p = q.front();
  21. q.pop();
  22. int i = p.first , j = p.second;
  23. if (valid(i , j-1)) {
  24. if (test )parent[i][j-1] = 'L';
  25. vis[i][j-1] = true;
  26. v[i][j-1] = v[i][j] + 1;
  27. q.push(make_pair(i, j-1));
  28. }
  29. if (valid(i , j+1)) {
  30. if (test )parent[i][j+1] = 'R';
  31. vis[i][j+1] = true;
  32. v[i][j+1] = v[i][j] + 1;
  33. q.push(make_pair(i, j+1));
  34. }
  35. if (valid(i-1 , j)) {
  36. if (test )parent[i-1][j] = 'U';
  37. vis[i-1][j] = true;
  38. v[i-1][j] = v[i][j] + 1;
  39. q.push(make_pair(i-1, j));
  40. }
  41. if (valid(i+1 , j)) {
  42. if (test )parent[i+1][j] = 'D';
  43. vis[i+1][j] = true;
  44. v[i+1][j] = v[i][j] + 1;
  45. q.push(make_pair(i+1, j));
  46. }
  47. }
  48. }
  49.  
  50. void solve() {
  51. ll x1 , y1 ;
  52. cin >> n >> m;
  53. matrix.assign(n , vector<char>(m));
  54. vis.assign(n, vector < bool > (m , false ));
  55. monster.assign(n , vector < ll >(m, 1e6));
  56. humain.assign(n , vector < ll >(m, 1e6));
  57. parent.assign(n , vector < char > (m ,'.'));
  58.  
  59. for (int i = 0 ; i < n ; i++) {
  60. for (int j = 0 ; j < m ; j++) cin >> matrix[i][j];
  61. }
  62.  
  63. queue <pair < ll , ll > > q;
  64. for (int i = 0 ; i < n ; i++) {
  65. for (int j = 0 ; j < m ; j++) {
  66. if (matrix[i][j] == 'M') {
  67. q.push(make_pair(i , j));
  68. monster[i][j] = 0;
  69. vis[i][j] = true;
  70. }
  71. }
  72. }
  73. bfs(q, monster ,0 );
  74.  
  75. q = queue < pair < ll , ll > >();
  76. vis.assign(n , vector <bool > (m , false));
  77. for (int i = 0 ; i < n ; i++) {
  78. for (int j = 0 ; j < m ; j++) {
  79. if (matrix[i][j] == 'A') {
  80. q.push(make_pair(i , j));
  81. humain[i][j] = 0;
  82. x1 = i ; y1= j ;
  83. vis[i][j] = true;
  84. }
  85. }
  86. }
  87. bfs(q, humain, 1 );
  88.  
  89. bool test = false;
  90. int x , y;
  91. for (int i = 0 ; i < n ; i++) {
  92. if (humain[i][0] < monster[i][0]) {
  93. x = i ; y = 0 ;
  94. test = 1 ;
  95. break;
  96. }
  97. else if (humain[i][m-1] < monster[i][m-1]) {
  98. x = i ; y = m-1 ;
  99. test = 1 ;
  100. break;
  101. }
  102. }
  103. for (int j = 0 ; j < m && !test; j++) {
  104. if (humain[0][j] < monster[0][j]) {
  105. x = 0 ; y = j;
  106. test = 1;
  107. break;
  108. }
  109. else if (humain[n-1][j] < monster[n-1][j]) {
  110. x = n-1 ; y = j;
  111. test = 1;
  112. break;
  113. }
  114. }
  115.  
  116. if (!test) {
  117. cout << "NO" << endl;
  118. return;
  119. }
  120. cout << "YES" << endl;
  121. string s ;
  122. while (parent[x][y] != '.') {
  123.  
  124. s+=parent[x][y] ;
  125. char c = parent[x][y] ;
  126. if ( c == 'R') {
  127. y -- ;
  128. }
  129. else if (c == 'L') {
  130. y ++ ;
  131. }
  132. else if (c == 'U') {
  133. x ++ ;
  134. }
  135. else x-- ;
  136. }
  137. reverse(all(s) ) ;
  138. cout <<s.size() <<endl << s<<endl ;
  139.  
  140. }
  141.  
  142.  
  143.  
  144. int main() {
  145. ios::sync_with_stdio(false);
  146. cin.tie(nullptr);
  147.  
  148. #ifndef ONLINE_JUDGE
  149. freopen("input.txt", "r", stdin);
  150. freopen("output.txt", "w", stdout);
  151. #endif
  152.  
  153. ll t = 1;
  154. //cin >> t;
  155.  
  156. while (t--) {
  157. solve();
  158. }
  159. }
  160.  
Success #stdin #stdout 0.01s 5324KB
stdin
Standard input is empty
stdout
NO