Cod sursa(job #2637442)

Utilizator OvidRata Ovidiu Ovid Data 22 iulie 2020 22:21:27
Problema Car Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.04 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 t, n, m, k, a[300010], q, l, r;
pii f, s;
int mat[510][510];
bool v[510][510];
int dir[510][510];
int d[510][510];
queue<pii> q45, q90;

void radial(){
vector<int> Y={1, 1, 1, -1, -1, -1, 0, 0};
vector<int> X={-1, 0, 1, -1, 0, 1, -1, 1};
vector<int> D={-135, -90, -45, 135, 90, 45, 180, 0};
v[f.ft][f.sc]=true;
d[f.ft][f.sc]=0;
for(int i=0; i<D.size(); i++){
    int dx=X[i], dy=Y[i];
    int x=f.sc+dx, y=f.ft+dy;
    while(x>=1 && y>=1 && x<=m && y<=n && (mat[y][x]==0) ){
        dir[y][x]=D[i];
        v[y][x]=true;
        d[y][x]=0;
        q45.push(mp(y, x));
        y+=dy; x+=dx;
    }
}
return;
}




pii cfs(int ccc){
int direction=ccc;
if(direction==(-180) ){direction=180;}
if(direction!=180){
    direction%=180;
}


if(direction==0){
    return mp(0 ,1);
}
if(direction==45){
    return mp(-1 ,1);
}
if(direction==-45){
    return mp(1 ,1);
}
if(direction==90){
    return mp(-1 ,0);
}
if(direction==-90){
    return mp(1 ,0);
}
if(direction==135){
    return mp(-1 ,-1);
}
if(direction==-135){
    return mp(1 ,-1);
}
if(direction==180){
    return mp(0 ,-1);
}
}



void parse(){


while( (!q45.empty()) || (!q90.empty()) ){
    while(!q45.empty()){
        pii ac=((q45.front()) ); q45.pop(); q90.push(ac);

        int y=ac.ft, x=ac.sc;
        pii c=cfs( (dir[y][x]+45) );
        int nd=(dir[y][x]+45);
        if(nd==-180){nd=180;}
        if(nd!=180){
            nd%=180;
        }
        int dy=c.ft, dx=c.sc;
        y+=dy; x+=dx;

        while(x>=1 && x<=m && y>=1 && y<=n && (mat[y][x]==0) && (!v[y][x]) ){
            dir[y][x]=nd;
            d[y][x]=d[ac.ft][ac.sc]+1;
            v[y][x]=true;
            q45.push(mp(y, x));
            y+=dy; x+=dx;
        }

        y=ac.ft, x=ac.sc;
        c=cfs( (dir[y][x]-45) );
        nd=(dir[y][x]-45);
        if(nd==-180){nd=180;}
        if(nd!=180){
            nd%=180;
        }
        dy=c.ft, dx=c.sc;
        y+=dy; x+=dx;

        while(x>=1 && x<=m && y>=1 && y<=n && (mat[y][x]==0) && (!v[y][x]) ){
            dir[y][x]=nd;
            d[y][x]=d[ac.ft][ac.sc]+1;
            v[y][x]=true;
            q45.push(mp(y, x));
            y+=dy; x+=dx;
        }


    }


        while(!q90.empty()){
        pii ac=((q90.front()) ); q90.pop();

        int y=ac.ft, x=ac.sc;
        pii c=cfs( (dir[y][x]+90) );
        int nd=(dir[y][x]+90);
        if(nd==-180){nd=180;}
        if(nd!=180){
            nd%=180;
        }
        int dy=c.ft, dx=c.sc;
        y+=dy; x+=dx;

        while(x>=1 && x<=m && y>=1 && y<=n && (mat[y][x]==0) && (!v[y][x]) ){
            dir[y][x]=nd;
            d[y][x]=d[ac.ft][ac.sc]+2;
            v[y][x]=true;
            q45.push(mp(y, x));
            y+=dy; x+=dx;
        }



         y=ac.ft, x=ac.sc;
        c=cfs( (dir[y][x]-90) );
         nd=(dir[y][x]-90);
        if(nd==-180){nd=180;}
        if(nd!=180){
            nd%=180;
        }
        dy=c.ft, dx=c.sc;
        y+=dy; x+=dx;

        while(x>=1 && x<=m && y>=1 && y<=n && (mat[y][x]==0) && (!v[y][x]) ){
            dir[y][x]=nd;
            d[y][x]=d[ac.ft][ac.sc]+2;
            v[y][x]=true;
            q45.push(mp(y, x));
            y+=dy; x+=dx;
        }



    }



}


}






int32_t main(){
INIT
cin>>n>>m;
cin>>f.ft>>f.sc>>s.ft>>s.sc;
for(int i=1; i<=n; i++){
    for(int j=1; j<=m; j++){
        cin>>mat[i][j];
    }
}
radial();
parse();


if(!v[s.ft][s.sc]){
    cout<<"-1"; return 0;
}
cout<<d[s.ft][s.sc];










return 0;
}