Advertisement
Zeinab_Hamdy

Untitled

Aug 30th, 2024 (edited)
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.45 KB | None | 0 0
  1. //  #### Zeinab
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define nl "\n"
  5. #define fi first
  6. #define se second
  7. #define pb push_back
  8. #define ll long long
  9. #define RV return void
  10. #define sz(x) int(x.size())
  11. #define all(v) v.begin(), v.end()
  12. #define rall(v) v.rbegin(), v.rend()
  13. #define cin(v) for(auto&x:v) cin >> x;
  14. #define cout(v) for(auto&x:v) cout << x << " ";
  15.  
  16. int n , m , X0 , Y0 , X1 , Y1;
  17. string str;
  18.         // w , e , n , s
  19. int dx[]= {0 , 0 ,-1 , 1};
  20. int dy[]= {-1 , 1 , 0 , 0};
  21. char turn[]={'w' , 'e' , 'n' , 's'};
  22.  
  23. vector < vector < int > > grid;
  24.  
  25. bool valid(int i , int j){
  26.     return i >=0 and j >=0 and i < n and j < m and !grid[i][j]  ;
  27. }
  28.  
  29.  
  30. int ret ;
  31.  
  32.  
  33.  
  34. void bfs(){
  35.     //  i , j , char , cost , (con)
  36.     queue < pair < pair < int , int > , pair < char , pair < int , int > > > > q;
  37.     vector < vector < int > > dis(n+1 , vector < int> (m+1 , -1));
  38.     q.push({{X0,Y0} , {str[0], {0 , 1}}});
  39.     dis[X0][Y0]=0;
  40.  
  41.     while(!q.empty()){
  42.         int i = q.front().fi.fi , j = q.front().fi.se ,
  43.         cs = q.front().se.se.fi , com = q.front().se.se.se;
  44.         char c = q.front().se.fi; q.pop();
  45.  
  46.  
  47.         for(int qw=0; qw < 4 ; qw++){
  48.             int x = i + dx[qw] , y =j + dy[qw];
  49.             if(valid(x,y) and dis[x][y] ==-1){
  50.                 int cost =1 , com2 =1;
  51.                 bool f=1;
  52.                 if((turn[qw] == 'e' or turn[qw] == 'w') and (c == 's' or c=='n')) f=0, cost =2;
  53.                 if((turn[qw] == 'n' or turn[qw] == 's') and (c == 'e' or c=='w')) f=0, cost =2;
  54.  
  55.  
  56.                 if(f){
  57.                     if(com < 3) com2 = com + 1 ,  cost=0;
  58.                 }
  59.  
  60.                 if(x == X1 and y == Y1){
  61.                     ret = cs + cost ;
  62.                     return ;
  63.                 }
  64.                 dis[x][y]=cost+cs;
  65.                 q.push({{x,y} , {turn[qw] , {cost + cs , com2}}});
  66.             }
  67.         }
  68.     }
  69.  
  70. }
  71.  
  72.  
  73.  
  74. void solve(){
  75.  
  76.     bool flag=0;
  77.  
  78. while(cin >> n >> m and n and m){
  79.     if(flag) cout << nl;
  80.     flag=1;
  81.     grid.assign(n,vector<int>(m,0));
  82.     for(auto& x : grid) cin(x);
  83.     cin >> X0 >> Y0 >> X1 >>Y1 >> str;
  84.     X0-- , Y0-- , X1 -- ,Y1--;
  85.     ret =-1;
  86.     bfs();
  87.  
  88.     cout << ret ;
  89.    
  90. }
  91.  
  92.  
  93.  
  94. }
  95.  
  96. int main(){
  97.     ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);  
  98.  
  99.  
  100.     int t=1;
  101.         // cin >> t ;
  102.     for(int i=1 ; i <= t ; i++){
  103.         // cout << "Case "<< i <<": " ;
  104.         solve();
  105.     }
  106.     return 0;
  107. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement