• Source
    1. #include<bits/stdc++.h>
    2.  
    3. using namespace std;
    4. typedef long long ll;
    5.  
    6. #define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
    7. #define all(x) (x).begin(), (x).end()
    8. #define sz(x) ((ll)(x).size())
    9. #define F first
    10. #define S second
    11.  
    12. // Bin search on ans? / DP ? what pattern : greedy / bit manipulation / graph ? dfs or bfs or pattern ? DSU //
    13. // Heap ? two heaps ? / Stack ? monotonic stack /deque ? //
    14. // If divide & conquer - merge sort / check for quick sort implementation as well
    15.  
    16. /* ---------------------------------------------------------------------------------------------------------------------------- */
    17.  
    18. int dx[4] = {1,0,0,-1};
    19. int dy[4] = {0,1,-1,0};
    20. string dirn = "RUDL";
    21.  
    22. bool isPossible(int x, int y, vector<string>& grid,vector<vector<bool>>& vis){
    23. int n = grid.size(), m = grid[0].size();
    24. if(x >= n || x < 0 || y >= m || y < 0 || grid[x][y] == '#' || vis[x][y]) return false;
    25. return true;
    26. }
    27.  
    28. void solve(){
    29. int n,m;
    30. cin>>n>>m;
    31. vector<string> grid(n);
    32. for(int i = 0;i<n;i++)
    33. cin>>grid[i];
    34.  
    35. queue<pair<int,int>> mon_q;
    36. pair<int,int> start;
    37. vector<vector<int>> mon_t(n,vector<int>(m,-1));
    38. vector<vector<bool>> vis(n,vector<bool>(m,false));
    39.  
    40. for(int i = 0;i<n;i++){
    41. for(int j = 0;j<m;j++){
    42. if(grid[i][j] == 'M'){
    43. mon_q.push({i,j});
    44. mon_t[i][j] = 0;
    45. }
    46. if(grid[i][j] == 'A') {
    47. start.F = i, start.S = j; // storing my initial location
    48. }
    49. }
    50. }
    51.  
    52. int cnt = 1;
    53.  
    54. //Multi-Source BFS
    55.  
    56. while(!mon_q.empty()){
    57. int grid_size = sz(mon_q);
    58. for(int i = 0;i<grid_size;i++){
    59. auto temp = mon_q.front();
    60. int x = temp.F, y = temp.S;
    61. mon_q.pop();
    62. for(int k = 0;k<4;k++){
    63. int nx = x + dx[k], ny = y + dy[k];
    64. if(isPossible(nx,ny,grid,vis)){
    65. mon_t[nx][ny] = cnt;
    66. vis[nx][ny] = true;
    67. mon_q.push({nx,ny});
    68. }
    69. }
    70. }
    71. cnt++;
    72. }
    73.  
    74. //----------------------------------------//
    75.  
    76. cnt = 1;
    77.  
    78. vis.resize(n,vector<bool>(m,false));
    79. vector<vector<int>> path(n,vector<int>(m,-1));
    80. queue<pair<int,int>> q;
    81.  
    82. q.push(start);
    83.  
    84. while(!q.empty()){
    85. auto temp = q.front();
    86. int x = temp.F, y = temp.S;
    87. q.pop();
    88. vis[x][y] = true;
    89.  
    90. for(int k = 0;k<4;k++){
    91. int nx = x + dx[k], ny = y + dy[k];
    92. if(isPossible(nx,ny,grid,vis)){
    93. if(cnt < mon_t[nx][ny]){
    94. path[nx][ny] = k;
    95. vis[nx][ny] = true;
    96. q.push({nx,ny});
    97.  
    98. // Checking if reached the border...
    99. if(nx == 0 || nx == n-1 || ny == 0 || ny == m-1){
    100. cout<<"YES\n";
    101. string print_path;
    102.  
    103. pair<int,int> xyz = {nx,ny};
    104. while(xyz != start){
    105. int idx = path[xyz.F][xyz.S];
    106. print_path.push_back(dirn[idx]);
    107. idx = 3 - idx;
    108. xyz.F += dx[idx];
    109. xyz.S += dy[idx];
    110. }
    111. reverse(all(print_path));
    112. cout<<print_path.size()<<"\n";
    113. cout<<print_path;
    114.  
    115. return;
    116. }
    117. }
    118. }
    119. }
    120. cnt++;
    121. }
    122. cout<<"NO";
    123. }
    124.  
    125. int main(){
    126. fast_cin();
    127. //#ifndef FELIX
    128. //freopen("input.txt","r",stdin);
    129. //freopen("output.txt","w",stdout);
    130. //#endif
    131. ll t = 1;
    132. //cin >> t;
    133. for(ll it = 1;it<=t;it++){
    134. // cout<<"Case #"<<it<<": ";
    135. solve();
    136. }
    137. return 0;
    138. }