fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 1e3 + 5;
  6. struct node{int r , c;}qin , qout;
  7. int n , m;
  8. char s[N][N];
  9. int dx[4] = {1 , -1 , 0 , 0};
  10. int dy[4] = {0 , 0 , 1 , -1};
  11. int dp1[N][N] , dp2[N][N];
  12. char pos[N][N];
  13. int ra , ca;
  14. queue<node> q1 , q2;
  15. vector<char> ans;
  16. int inside(int x , int y){
  17.     return 0 <= x && x < n && 0 <= y && y < m;
  18. }
  19. int ok = 0;
  20. /// check if valid path exists
  21. void dfs(int r , int c){
  22.     if(r == 0 || r == n - 1|| c == 0 || c == m - 1){
  23.         if(dp1[r][c] > dp2[r][c]){
  24.             cout << "YES" << endl;
  25.             ans.emplace_back(pos[r][c]);
  26.             ok = 1;
  27.             return;
  28.         }
  29.     }
  30.     for(int i = 0; i < 4; ++i){
  31.         int r2 = r + dx[i];
  32.         int c2 = c + dy[i];
  33.         if(inside(r2 , c2)){
  34.             if(pos[r2][c2] == '.'){
  35.                 if(dp1[r2][c2] > dp2[r2][c2] && s[r2][c2] != '#'){
  36.                     if(i == 0) pos[r2][c2] = 'D';
  37.                     if(i == 1) pos[r2][c2] = 'U';
  38.                     if(i == 2) pos[r2][c2] = 'R';
  39.                     if(i == 3) pos[r2][c2] = 'L';
  40.                     dfs(r2 , c2);
  41.                     if(ok) {ans.emplace_back(pos[r][c]);break;}
  42.                 }
  43.             }
  44.         }
  45.     }
  46. }
  47. void solve(){
  48.     /// min distance from a monster
  49.     while(q1.size()){
  50.         qout = q1.front();
  51.         q1.pop();
  52.         int r= qout.r , c = qout.c;
  53.         for(int i = 0; i < 4; ++i){
  54.             int r2 = qout.r + dx[i];
  55.             int c2 = qout.c + dy[i];
  56.             if(inside(r2 , c2)){
  57.                 if(dp1[r2][c2] > dp1[r][c] + 1 && s[r2][c2] != '#'){
  58.                     dp1[r2][c2] = dp1[r][c] + 1;
  59.                     qin.r = r2 , qin.c = c2;
  60.                     q1.push(qin);
  61.                 }
  62.             }
  63.         }
  64.     }
  65.     qin.r = ra , qin.c = ca;
  66.     q2.push(qin);
  67.     /// min distance from A
  68.     while(!q2.empty()){
  69.         qout = q2.front();
  70.         q2.pop();
  71.         int r= qout.r , c = qout.c;
  72.         for(int i = 0; i < 4; ++i){
  73.             int r2 = qout.r + dx[i];
  74.             int c2 = qout.c + dy[i];
  75.             if(inside(r2 , c2)){
  76.                 if(dp2[r2][c2] > dp2[r][c] + 1 && s[r2][c2] != '#'){
  77.                     dp2[r2][c2] = dp2[r][c] + 1;
  78.                     q2.push({r2 , c2});
  79.                 }
  80.             }
  81.         }
  82.     }
  83.     dfs(ra , ca);
  84. }
  85. int main (){
  86.     ios_base::sync_with_stdio(false); cin.tie(0);
  87.     cin >> n >> m;
  88.     for(int i = 0; i < n; ++i){
  89.         for(int j = 0; j < m; ++j){
  90.             cin >> s[i][j];
  91.         }
  92.     }
  93.     for(int i = 0; i < n; ++i){
  94.         for(int j = 0; j < m; ++j){
  95.             dp1[i][j] = dp2[i][j] = 1e9;
  96.         }
  97.     }
  98.     for(int i = 0; i < n; ++i){
  99.         for(int j = 0; j < m; ++j){
  100.             if(s[i][j] == 'M'){
  101.                 q1.push({i , j});
  102.                 dp1[i][j] = 0;
  103.             }
  104.             if(s[i][j] == 'A') {ra = i; ca = j; dp2[i][j] = 0;}
  105.         }
  106.     }
  107.     for(int i = 0; i < n; ++i){
  108.         for(int j = 0; j < m; ++j){
  109.             pos[i][j] = '.';
  110.         }
  111.     }
  112.     solve();
  113.     if(ans.empty()){ cout << "NO"; return 0;}
  114.     cout << ans.size() - 1<< endl;
  115.     reverse(ans.begin() , ans.end());
  116.     for(int i = 1; i < ans.size(); ++i) cout << ans[i];
  117. return 0;
  118. }
  119.  
Success #stdin #stdout 0s 4500KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
NO
https://ideone.com/jgR1tm
language:
C++ (gcc 8.3)
created:
5 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!