Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // #### Zeinab
- #include<bits/stdc++.h>
- using namespace std;
- #define nl "\n"
- #define fi first
- #define se second
- #define pb push_back
- #define ll long long
- #define RV return void
- #define sz(x) int(x.size())
- #define all(v) v.begin(), v.end()
- #define rall(v) v.rbegin(), v.rend()
- #define cin(v) for(auto&x:v) cin >> x;
- #define cout(v) for(auto&x:v) cout << x << " ";
- int n , m , X0 , Y0 , X1 , Y1;
- string str;
- // w , e , n , s
- int dx[]= {0 , 0 ,-1 , 1};
- int dy[]= {-1 , 1 , 0 , 0};
- char turn[]={'w' , 'e' , 'n' , 's'};
- vector < vector < int > > grid;
- bool valid(int i , int j){
- return i >=0 and j >=0 and i < n and j < m and !grid[i][j] ;
- }
- int ret ;
- void bfs(){
- // i , j , char , cost , (con)
- queue < pair < pair < int , int > , pair < char , pair < int , int > > > > q;
- vector < vector < int > > dis(n+1 , vector < int> (m+1 , -1));
- q.push({{X0,Y0} , {str[0], {0 , 1}}});
- dis[X0][Y0]=0;
- while(!q.empty()){
- int i = q.front().fi.fi , j = q.front().fi.se ,
- cs = q.front().se.se.fi , com = q.front().se.se.se;
- char c = q.front().se.fi; q.pop();
- for(int qw=0; qw < 4 ; qw++){
- int x = i + dx[qw] , y =j + dy[qw];
- if(valid(x,y) and dis[x][y] ==-1){
- int cost =1 , com2 =1;
- bool f=1;
- if((turn[qw] == 'e' or turn[qw] == 'w') and (c == 's' or c=='n')) f=0, cost =2;
- if((turn[qw] == 'n' or turn[qw] == 's') and (c == 'e' or c=='w')) f=0, cost =2;
- if(f){
- if(com < 3) com2 = com + 1 , cost=0;
- }
- if(x == X1 and y == Y1){
- ret = cs + cost ;
- return ;
- }
- dis[x][y]=cost+cs;
- q.push({{x,y} , {turn[qw] , {cost + cs , com2}}});
- }
- }
- }
- }
- void solve(){
- bool flag=0;
- while(cin >> n >> m and n and m){
- if(flag) cout << nl;
- flag=1;
- grid.assign(n,vector<int>(m,0));
- for(auto& x : grid) cin(x);
- cin >> X0 >> Y0 >> X1 >>Y1 >> str;
- X0-- , Y0-- , X1 -- ,Y1--;
- ret =-1;
- bfs();
- cout << ret ;
- }
- }
- int main(){
- ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
- int t=1;
- // cin >> t ;
- for(int i=1 ; i <= t ; i++){
- // cout << "Case "<< i <<": " ;
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement