Advertisement
Zeinab_Hamdy

Untitled

Oct 16th, 2023
663
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.59 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define nl "\n"
  4. #define fi first
  5. #define se second
  6. #define pb push_back
  7. #define ll long long
  8. #define ull unsigned ll
  9. #define RV  return void
  10. // #define inf 2000000000
  11. #define sz(x) int(x.size())
  12. #define all(v) v.begin(), v.end()
  13. #define rall(v) v.rbegin(), v.rend()
  14. #define Mini(x) *min_element(all(x))
  15. #define Maxi(x) *max_element(all(x))
  16. #define fixed(n) fixed << setprecision(n)
  17. #define ceil(w, m) (((w) / (m)) + ((w) % (m) ? 1 : 0))
  18. #define cin(v) for (auto&i:v) cin >> i;
  19. #define cout(v) for (auto&i:v) cout << i << " ";
  20. #define clr(memo, x) memset(memo, x, sizeof memo)
  21. #define updmin(a, b) a = min(a, b)
  22. #define updmax(a, b) a = max(a, b)
  23. #define vi vector < int >
  24. #define vl vector < ll >
  25. #define vc vector < char >
  26. #define vs vector < string >
  27. #define v2i vector < vector < int > >
  28. #define v2l vector < vector < int > >
  29. #define seti set < int >
  30. #define setl set < ll >
  31. #define mapii map < int , int >
  32. #define mapll map < ll , ll >
  33. #define mapli map < ll , int >
  34. #define mapci map < char , int >
  35. #define mapsi map < string , int >
  36. #define pll pair < ll , ll >
  37. #define pii pair < int , int >
  38. #define range(l,r,x) for(int i=l ; i < r ; i+=x)
  39. #define FastCode ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  40. vector < string > ternary= {"NO\n" , "YES\n"};
  41.  
  42. void  Zainab(){
  43.             #ifndef ONLINE_JUDGE
  44.               freopen("input.txt", "r", stdin);
  45.               freopen("output.txt", "w", stdout);
  46.             #endif
  47. }
  48.  
  49.  
  50. /*================================  solution  ================================ */
  51.  
  52. const int N = 1e3+5;
  53. char arr[N][N];
  54.  
  55.  
  56. int dx[] = {1 , -1 , 0 , 0};
  57. int dy[] = {0 , 0 , 1 , -1};
  58. char C[] = {'D' , 'U' , 'R' , 'L'};
  59.  
  60. bool vis[N][N];
  61. int n , m;
  62. string path , ans = "-1";
  63.  
  64.  
  65.  
  66. bool valid (int x , int y  ){
  67.     return x >= 0 && x < n && y >= 0 && y < m && arr[x][y] != '#' && !vis[x][y];
  68. }
  69.  
  70.  
  71. void bfs(int ax  , int ay , int bx , int by){
  72.  
  73.     queue < pair < int , int > > q;
  74.     q.push({ax , ay});
  75.     vis[ax][ay] = 1;
  76.    
  77.     while(!q.empty()){
  78.         auto p = q.front();
  79.         q.pop();
  80.         int x = p.fi , y = p.se;
  81.         for(int i =0 ; i < 4 ; i++){
  82.             int nx = x + dx[i] , ny = y + dy[i];
  83.            
  84.             if(valid(nx , ny)){
  85.                 vis[nx][ny] = 1;
  86.                 path += C[i];
  87.                 q.push({nx,ny});
  88.                 if(nx == bx && ny == by){
  89.                     // cout << x << " " << y << " " << nx << " " << ny << nl;
  90.                     // cout << path << nl;
  91.                    
  92.                     path.pop_back();
  93.                     if(sz(path) < sz(ans) or ans =="-1"){
  94.                         ans = path ;
  95.                         path="";
  96.                     }
  97.                    
  98.                 }
  99.                
  100.             }
  101.         }
  102.     }
  103. }
  104.  
  105.  
  106.  
  107. void myCode(){
  108.  
  109.  
  110.  
  111.     cin >> n >> m ;
  112.     int aX  , aY , bX , bY;
  113.     for(int i =0 ;  i < n ; i++){
  114.         for(int j =0 ; j < m ; j++){
  115.             cin >> arr[i][j];
  116.  
  117.             if(arr[i][j]=='A')
  118.                 aX = i ,  aY = j;
  119.             else if(arr[i][j]=='B')
  120.                 bX = i , bY = j;
  121.            
  122.         }
  123.     }
  124.  
  125.  
  126.     bfs(aX , aY , bX , bY);
  127.     cout << sz(ans) << nl;
  128.     cout << ans ;
  129. }
  130.  
  131.  
  132. int main(){
  133.  
  134.                                 FastCode ;
  135.                      Zainab() ;
  136.  
  137.             int testCase=1;
  138.                 // cin >> testCase ;
  139.             for(int i=1 ; i<= testCase ; i++){
  140.                 //  cout << "Case #" << i << ": ";
  141.                 myCode();
  142.             }
  143.      
  144.  
  145.     return 0;
  146. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement