fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define mod 1000000007
  5. #define pb push_back
  6. #define mp make_pair
  7. #define vi vector<int>
  8. #define onesbits(x) __builtin_popcountll(x)
  9. #define zerobits(x) __builtin_ctzll(x)
  10. #define sp(x, y) fixed << setprecision(y) << x
  11. #define w(x)  int x;cin >> x;while (x--)
  12. #define tk(x) int x;cin >> x;
  13. #define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  14. #ifndef ONLINE_JUDGE
  15. #define debug(x) cerr<< #x <<" ";_print(x);cerr<<endl;
  16. #else
  17. #define debug(x)
  18. #endif
  19. template <class T> void _print(T t){cerr<<t;}
  20. template <class T> void _print(vector < vector <T> > v){cerr<<"[\n";for(int l=0;l<v.size();l++){{for(int k=0;k<v[l].size();k++)cerr<<v[l][k]<<" ";}cerr<<"\n";}cerr<<"]";}
  21.  
  22. queue<pair<int,int>>que;
  23. vector<vector<int>>vx;
  24. vector<vector<int>>vy;
  25. vector<vector<int>>dis;
  26. int c=0,len=0;
  27. void bfs(int i,int j,int n,int m,vector<vector<char>>& v,int l,vector<vector<bool>>& vis){
  28.     vis[i][j]=true;
  29.     if(i+1<n){
  30.         if(v[i+1][j]=='.' && vis[i+1][j]==false) {
  31.             vis[i+1][j]=true;
  32.             dis[i+1][j]=dis[i][j]+1;
  33.             vx[i+1][j]=i;
  34.             vy[i+1][j]=j;
  35.             que.push(mp(i+1,j));
  36.         }
  37.         else if(v[i+1][j]=='B'){
  38.              dis[i+1][j]=dis[i][j]+1;
  39.              vx[i+1][j]=i;
  40.              vy[i+1][j]=j;
  41.             c=1;
  42.             return;
  43.         }
  44.     }
  45.      if(j+1<m){
  46.  
  47.          if(v[i][j+1]=='.' && vis[i][j+1]==false){
  48.              vis[i][j+1]=true;
  49.              dis[i][j+1]=dis[i][j]+1;
  50.              vx[i][j+1]=i;
  51.              vy[i][j+1]=j;
  52.              que.push(mp(i,j+1));
  53.          }
  54.          else if(v[i][j+1]=='B'){
  55.             dis[i][j+1]=dis[i][j]+1;
  56.             c=1;
  57.              vx[i][j+1]=i;
  58.              vy[i][j+1]=j;
  59.             return;
  60.         }
  61.      }
  62.      if(i-1>=0){
  63.  
  64.          if(v[i-1][j]=='.' && vis[i-1][j]==false){
  65.              vis[i-1][j]=true;
  66.              dis[i-1][j]=dis[i][j]+1;
  67.              vx[i-1][j]=i;
  68.              vy[i-1][j]=j;
  69.              que.push(mp(i-1,j));
  70.          }
  71.          else if(v[i-1][j]=='B'){
  72.              dis[i-1][j]=dis[i][j]+1;
  73.              vx[i-1][j]=i;
  74.              vy[i-1][j]=j;
  75.             c=1;
  76.             return;
  77.         }
  78.      }
  79.      if(j-1>=0){
  80.  
  81.          if(v[i][j-1]=='.' && vis[i][j-1]==false){
  82.              vis[i][j-1]=true;
  83.              dis[i][j-1]=dis[i][j]+1;
  84.             vx[i][j-1]=i;
  85.             vy[i][j-1]=j;
  86.              que.push(mp(i,j-1));
  87.          }
  88.          else if(v[i][j-1]=='B'){
  89.              dis[i][j-1]=dis[i][j]+1;
  90.             vx[i][j-1]=i;
  91.             vy[i][j-1]=j;
  92.             c=1;
  93.             return;
  94.         }
  95.      }
  96. }
  97. int32_t main(){
  98. fast
  99.  
  100.  
  101. #ifndef ONLINE_JUDGE
  102.  
  103.  
  104.     freopen("input.txt","r",stdin);
  105.     freopen("output.txt","w",stdout);
  106.     freopen("error.txt","w",stderr);
  107.  
  108.  
  109. #endif
  110.  
  111.  
  112. int n,m;
  113. cin>>n>>m;
  114. vector<vector<bool>>vis(n,vector<bool>(m,false));
  115. vector<vector<char>>v(n,vector<char>(m));
  116. dis.resize(n);
  117. vx.resize(n);
  118. vy.resize(n);
  119. int x,y,x1,y1;
  120. for(int i=0;i<n;i++){
  121.     dis[i].resize(m,0);
  122.     vx[i].resize(m,0);
  123.     vy[i].resize(m,0);
  124.    for(int j=0;j<m;j++){
  125.       cin>>v[i][j];
  126.       if(v[i][j]=='A'){
  127.           x=i;
  128.           y=j;
  129.       }
  130.       else if(v[i][j]=='B'){
  131.           x1=i;
  132.           y1=j;
  133.       }
  134.    }
  135. }
  136.  
  137. que.push(mp(x,y));
  138. while(!que.empty()){
  139.     x=que.front().first;
  140.     y=que.front().second;
  141.     que.pop();
  142.     debug(dis);
  143.     len++;
  144.     bfs(x,y,n,m,v,len,vis);
  145.     if(c==1){
  146.         break;
  147.     }
  148. }
  149.  
  150. int distance=dis[x1][y1];
  151. int z=distance;
  152. string ans="";
  153. while(distance--){
  154.     int px=vx[x1][y1];
  155.     int py=vy[x1][y1];
  156.     if(x1-1==px){
  157.         ans="D"+ans;
  158.         x1=x1-1;
  159.     }
  160.     else if(x1+1==px){
  161.          ans="U"+ans;
  162.          x1=x1+1;
  163.     }
  164.     else if(y1-1==py) {
  165.         ans="R"+ans;
  166.         y1=y1-1;
  167.     }
  168.     else if(y1+1==py) {
  169.         ans="L"+ans;
  170.         y1=y1+1;
  171.     }
  172.  
  173. }
  174.  
  175.  
  176.  
  177.  if(z==0){
  178.      cout<<"NO"<<"\n";
  179.  }
  180.  else{
  181.       cout<<"YES"<<"\n"<<z<<"\n"<<ans<<"\n";
  182.  }
  183.  
  184. return 0;
  185. }
Success #stdin #stdout 0s 5548KB
comments (?)
stdin
copy 
10 10
.#........
..........
..........
........#.
..........
..........
.........#
..........
.......AB.
.....#....
stdout
copy 
YES
1
R
https://ideone.com/zaVKcB
language:
C++14 (gcc 8.3)
created:
2 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!