Cod sursa(job #2765314)

Utilizator OvidRata Ovidiu Ovid Data 26 iulie 2021 12:52:30
Problema Car Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.25 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, a[501][501];

struct edge{
    int i=0, j=0, dr=0, d=0;
};

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


int si, sj, fi, fj;



//0-1 bfs

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


queue<nod> q[ 250010  ];
int d[501][501][8];
bool v[501][501][8];

void 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;
        d[f.i ][f.j][f.dr]=D;
        for(auto e:g[f.i][f.j][f.dr]){
            nod n0; n0.i=e.i, n0.j=e.j, n0.dr=e.dr; int d=e.d;
            if(v[n0.i][n0.j][n0.dr]==true ){continue;}
            q[D+d].push(n0);
        }
    }
}


}




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';
    }
}

vector<int> X={1, 1, 0, -1, -1, -1, 0, 1};
vector<int> Y={0, -1,-1, -1, 0, 1, 1, 1};
for(int i=1; i<=n; i++){
    for(int j=1; j<=m; j++){
        if(a[i][j]==0){
            for(int dr=1; dr<=8; dr++){
                edge e; e.i=i, e.j=j, e.dr=dr%8, e.d=1;
                g[i][j][dr-1].pb(e);
                e.dr=dr-i;
                g[i][j][dr%8].pb(e);

                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);
                }
            }
        }
    }
}
bfs();
int res=1e9;
for(int dr=0; dr<=7; dr++){
    res=min(res, d[fi][fj][dr]);
}
cout<<res<<"\n";





return 0;
}