fork(1) download 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define pb push_back
  4. #define mod 1000000007
  5. #define inf 100000000000000000
  6. #define ar array
  7. #define fast ios::sync_with_stdio(false); cin.tie(0)
  8. #define setpres(x) fixed<<setprecision(x)
  9. using namespace std;
  10. int m,n;
  11. string s[1000];
  12. int dx[]={0,0,-1,1};
  13. int dy[]={1,-1,0,0};
  14. queue<ar<int,2>> q;
  15. map<ar<int,2>,ar<int,2>> par;
  16. map<ar<int,2>,int> vis;
  17. string ans;
  18. bool ok(int i, int j)
  19. {
  20.     return i>=0 && i<m && j>=0 && j<n && !vis[{i,j}] && s[i][j]!='#';
  21. }
  22. int32_t main()
  23. {
  24.     cin>>m>>n;
  25.     for(int i=0;i<m;i++)
  26.         cin>>s[i];
  27.     int ia,ib, fx,fy;
  28.     for(int i=0;i<m;i++)
  29.     {
  30.         for(int j=0;j<n;j++)
  31.         {
  32.             if(s[i][j]=='A')
  33.             {
  34.                 ia=i;
  35.                 ib=j;
  36.             }
  37.             if(s[i][j]=='B')
  38.             {
  39.                 fx=i;
  40.                 fy=j;
  41.             }
  42.         }
  43.     }
  44.     par[{ia,ib}]={-1,-1};
  45.     q.push({ia,ib});
  46.     vis[{ia,ib}]=1;
  47.     while(!q.empty())
  48.     {
  49.         auto x=q.front();
  50.         q.pop();
  51.         if(x[0]==fx && x[1]==fy)
  52.             break;
  53.         int i=x[0];
  54.         int j=x[1];
  55.         for(int k=0;k<4;k++)
  56.         {
  57.             if(ok(i+dx[k],j+dy[k]))
  58.             {
  59.                 q.push({i+dx[k],j+dy[k]});
  60.                 vis[{i+dx[k],j+dy[k]}]=1;
  61.                 par[{i+dx[k],j+dy[k]}]={x[0],x[1]};
  62.             }
  63.         }
  64.     }
  65.     if(par.find({fx,fy})==par.end())
  66.     {
  67.         cout<<"NO";
  68.         return 0;
  69.     }
  70.     cout<<"YES\n";
  71.     while(1)
  72.     {
  73.         if(par[{fx,fy}][0]==-1)
  74.             break;
  75.         int f1=par[{fx,fy}][0];
  76.         int f2=par[{fx,fy}][1];
  77.         if(f2==fy+1)
  78.             ans+='L';
  79.         else if(f2==fy-1)
  80.             ans+='R';
  81.         else if(f1==fx+1)
  82.             ans+='U';
  83.         else
  84.             ans+='D';
  85.         fx=f1;
  86.         fy=f2;
  87.     }
  88.     cout<<ans.length()<<"\n";
  89.     for(int i=ans.length()-1;i>=0;i--)
  90.         cout<<ans[i];
  91. }
Success #stdin #stdout 0.01s 4392KB
comments (?)
stdin 
Standard input is empty
stdout 
NO
https://ideone.com/1omthz
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!