fork download
copy 
  1. // SIGMA BOY hihihihihihihi
  2.  
  3. #define se second
  4. #define fi first
  5. #define pb push_back
  6. #define pob pop_back
  7. #define bitebi __builtin_popcountll
  8. #include <bits/stdc++.h>
  9.  
  10. using namespace std ;
  11. typedef long long ll;
  12. typedef long double ld;
  13. typedef pair<ll,ll> pll;
  14. typedef pair<int,int> pii;
  15.  
  16. const ll Mod = 1e9+7;
  17. const ll Maxn = 1e3+100;
  18. const ll oo = 1e18;
  19. const ll inf = 1e9;
  20.  
  21. char c[Maxn][Maxn];
  22. int d[Maxn][Maxn], n , m , flag=0,DistanceMin;
  23. pii locationA,locationB;
  24. int dx[4] = {0,0,1,-1};
  25. int dy[4] = {-1,1,0,0};
  26. char dc[4] ={'R','L','U','D'};
  27. string res;
  28.  
  29. bool Check ( int x , int y )
  30. {
  31.     // return true neu co the den duoc o do
  32.     // false neu nguoc lai
  33.     if(x<1||x>n||y<1||y>m||c[x][y]=='#'||d[x][y]!=inf) return false;
  34.     return true;
  35. }
  36.  
  37. void bfs ( pair<int,int> cur )
  38. {
  39.     queue<pii> q;
  40.     q.push(cur);
  41.     d[cur.fi][cur.se] = 0 ;
  42.     while(!q.empty()){
  43.         cur = q.front(); q.pop();
  44.         for (int i = 0 ; i < 4; ++i) {
  45.             pii Newlocation = {cur.fi+dx[i],cur.se+dy[i]};
  46.             if(Check(Newlocation.fi,Newlocation.se))
  47.             {
  48.                 d[Newlocation.fi][Newlocation.se]=d[cur.fi][cur.se]+1;
  49.                 q.push(Newlocation);
  50.             }
  51.         }
  52.     }
  53. }
  54.  
  55. void dfs (pii cur, int leng)
  56. {
  57.     if(leng==-1)
  58.     {
  59.         reverse(res.begin(),res.end());
  60.         cout << res;
  61.         return;
  62.     }
  63.     for (int i = 0 ; i < 4; ++i)
  64.     {
  65.         pii Newlocation = {cur.fi+dx[i],cur.se+dy[i]};
  66.         if(Newlocation.fi<1||Newlocation.fi>n
  67.            ||Newlocation.se<1||Newlocation.se>m) continue;
  68.         if(d[Newlocation.fi][Newlocation.se]==leng)
  69.         {
  70.             res.pb(dc[i]);
  71.             dfs(Newlocation,leng-1);
  72.             break;
  73.         }
  74.     }
  75. }
  76.  
  77. void Do()
  78. {
  79.     cin >> n >> m ;
  80.     for (int i = 1 ; i <= n ; ++i)
  81.         for (int j = 1 ; j <= m ; ++j) {
  82.             cin >> c[i][j],d[i][j]=inf;
  83.             if(c[i][j]=='A') locationA = {i,j};
  84.             if(c[i][j]=='B') locationB = {i,j};
  85.         }
  86.     bfs(locationA);
  87.     DistanceMin = d[locationB.fi][locationB.se];
  88.     if(DistanceMin==inf)
  89.     {
  90.         cout << "NO" << '\n';
  91.         return;
  92.     }
  93.     cout << "YES\n" << DistanceMin << '\n';
  94.     dfs(locationB,DistanceMin-1);
  95. }
  96.  
  97. signed main ()
  98. {
  99.     ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  100. #define task "test"
  101.     if(fopen(task".inp", "r")){
  102.         freopen(task".inp", "r", stdin);
  103.         freopen(task".out", "w", stdout);
  104.     }
  105.     int ntest=1;
  106.     while(ntest--) Do();
  107.  
  108.     cerr<<"\nTime elapsed: "<<1000*clock()/CLOCKS_PER_SEC<<"ms\n";
  109. }
  110.  
Success #stdin #stdout #stderr 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
YES
0
stderr
copy 
Time elapsed: 4ms
https://ideone.com/NhReOe
language:
C++14 (gcc 8.3)
created:
5 days 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!