Advertisement
Zeinab_Hamdy

Untitled

Oct 7th, 2023
601
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.64 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.  
  53. const ll N = 1e3 + 5 , inf = 1e18;
  54.  
  55.  
  56.  
  57. int n , m , X1 , X2 , Y1 , Y2 ;
  58.  
  59. char arr[N][N];
  60.  
  61.  
  62. int dx[]={ -1 , 1 ,  0 , 0 };
  63. int dy[]={  0 , 0 ,  1 , -1};
  64. char C[] ={ 'U' , 'D' , 'R' , 'L' };
  65.  
  66. bool valid(int x , int y){
  67.     return x >=0 and y>=0 and x < n and y < m ;
  68. }
  69.  
  70.  
  71. ll dp[N+10][N+10];
  72.  
  73.  
  74.  
  75. ll rec(int x , int y ){
  76.  
  77.     if(x==X2 and y==Y2) return 0 ;
  78.     if(!valid(x,y) or arr[x][y]=='#') return inf ;
  79.  
  80.     ll& ret = dp[x][y];
  81.     if(~ret) return ret;
  82.  
  83.     ret = inf;
  84.     for(int i =0 ; i < 4 ; i++){
  85.         int newX = x + dx[i] , newY = y + dy[i];
  86.         if(valid(newX , newY) and arr[newX][newY]!='#')
  87.             ret = min(ret , 1+ rec(newX , newY));
  88.     }
  89.     return ret ;
  90. }
  91.  
  92.  
  93. void build(int x , int y ){
  94.    
  95.         if(x==X2 and y==Y2) return ;
  96.         if(!valid(x,y) or arr[x][y]=='#') return ;
  97.    
  98.         ll ret = inf;
  99.         for(int i =0 ; i < 4 ; i++){
  100.             int newX = x + dx[i] , newY = y + dy[i];
  101.             if(valid(newX , newY) and arr[newX][newY]!='#')
  102.                ret = min(ret , 1 +rec(newX , newY));
  103.         }
  104.  
  105.         for(int i =0 ; i < 4 ; i++){
  106.             int newX = x + dx[i] , newY = y + dy[i];
  107.             if(valid(newX , newY) and arr[newX][newY]!='#' and ret == 1 + rec(newX , newY)){
  108.                 cout << C[i];
  109.                 build(newX , newY);
  110.                 return ;
  111.             }
  112.         }
  113. }
  114.  
  115.  
  116. void myCode(){
  117.  
  118. cin >> n >> m ;
  119.  
  120. for(int i =0 ; i < n ; i++){
  121.     for(int j =0 ; j < m ; j++){
  122.         cin >> arr[i][j];
  123.         if(arr[i][j]=='A') X1=i , Y1=j;
  124.         else if(arr[i][j]=='B') X2 = i , Y2 = j;
  125.     }
  126. }
  127.  
  128. clr(dp , -1);
  129.  
  130.  
  131.  
  132. ll ans = inf ;
  133.  
  134. ans = min(ans , rec(X1 , Y1));
  135.  
  136. if(ans == inf) RV(cout << "NO");
  137.  
  138.  
  139. cout << "YES\n" << ans << nl;
  140.  
  141. build(X1,Y1);
  142.  
  143.  
  144.  
  145. }
  146.  
  147.  
  148. int main(){
  149.                                    FastCode ;
  150.                                    Zainab() ;
  151.  
  152.  
  153.  
  154.  
  155.  
  156.         int testCase=1;
  157.             //  cin >> testCase ;
  158.         for(int i=1 ; i<= testCase ; i++){
  159.             myCode();
  160.         }
  161.  
  162.  
  163.     return 0;
  164. }
  165.  
  166.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement