Cod sursa(job #2765430)

Utilizator OvidRata Ovidiu Ovid Data 26 iulie 2021 20:24:30
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.49 kb
#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
//#define int ll


ifstream fin("car.in"); ofstream fout("car.out");
#define cin fin
#define cout fout


int n, m;


//vector<edge> g[501][501][8];


int si, sj, fi, fj;
vector<int> X={1, 1, 0, -1, -1, -1, 0, 1};
vector<int> Y={0, -1,-1, -1, 0, 1, 1, 1};


//0-1 bfs

struct nod{
    short int i=0, j=0, dr=0;
};


queue<nod> q[2];

bool v[501][501][8];

bool bfs(){
nod n0; n0.i=si, n0.j=sj;
for(int dr=0; dr<=7; dr++){
    n0.dr=dr;
    q[0].push(n0);
}


for(int D=0; D<=250000; D++){
    while(!q[0].empty()){
        auto f=q[0].front(); q[0].pop();
        if( v[f.i][f.j][f.dr]==false ){continue;}
        v[f.i][f.j][f.dr]=false;
        if( (f.i==fi) && (f.j==fj) ){
            cout<<D<<"\n";return true;
        }
        //d[f.i ][f.j][f.dr]=D;


               int dr=f.dr, j=f.j, i=f.i;
                if( ( (X[dr%8]+j)<=m ) && ( (Y[dr%8]+i)<=n ) && (  v[ Y[dr%8]+i ][X[dr%8]+j ][dr]==1   ) &&  ( (X[dr%8]+j)>=1 ) && ( (Y[dr%8]+i)>=1 )   ){
                    //edge e; e.i=Y[dr%8]+i, e.j=X[dr%8]+j, e.dr=dr%8, e.d=0;
                    //g[i][j][dr%8].pb(e);
                    if(v[ Y[dr%8]+i ][ X[dr%8]+j ][dr]==1){
                        nod n0; n0.i=Y[dr%8]+i, n0.j=X[dr%8]+j, n0.dr=dr;
                        q[0].push(n0);
                    }
                }
             dr=f.dr-1;
            if(dr<0){
                dr=7;
            }
            if(v[i][j][dr]==1){
                    nod n0; n0.i=i, n0.j=j, n0.dr=dr;
                q[1].push(n0);
            }
            dr=f.dr+1; dr%=8;
            if(v[i][j][dr]==1){
                    nod n0; n0.i=i, n0.j=j, n0.dr=dr;
                q[1].push(n0);
            }
    }
    while(!q[1].empty()){
        q[0].push(q[1].front()); q[1].pop();
    }
}

return false;
}




int32_t main(){
INIT


cin>>n>>m;
cin>>si>>sj>>fi>>fj;
for(int i=1; i<=n; i++){
    for(int j=1; j<=m; j++){
        char c;cin>>c;
        for(int dr=0; dr<=7 ;dr++){
            v[i][j][dr]=(c-'0')^1;
        }
    }
}
//cout<<0;
//return 0;


if(bfs()){return 0;};
cout<<"-1\n";





return 0;
}