Cod sursa(job #2765318)

Utilizator OvidRata Ovidiu Ovid Data 26 iulie 2021 13:03:10
Problema Car Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.34 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; bool a[501][501];


//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[ 250010  ];

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[D].empty()){
        auto f=q[D].front(); q[D].pop();
        if( v[f.i][f.j][f.dr]==true ){continue;}
        v[f.i][f.j][f.dr]=true;
        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 ) && (  a[ Y[dr%8]+i ][X[dr%8]+j ]==0   ) &&  ( (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]){
                        nod n0; n0.i=Y[dr%8]+i, n0.j=X[dr%8]+j, n0.dr=dr;
                        q[D+0].push(n0);
                    }
                }
             dr=f.dr-1;
            if(dr<0){
                dr=7;
            }
            if(!v[i][j][dr]){
                    nod n0; n0.i=i, n0.j=j, n0.dr=dr;
                q[D+1].push(n0);
            }
            dr=f.dr+1; dr%=8;
            if(!v[i][j][dr]){
                    nod n0; n0.i=i, n0.j=j, n0.dr=dr;
                q[D+1].push(n0);
            }
    }
}

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;
        a[i][j]=c-'0';
    }
}



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





return 0;
}