Cod sursa(job #2637155)

Utilizator OvidRata Ovidiu Ovid Data 21 iulie 2020 15:57:40
Problema Car Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.42 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, mat[510][510];
pii f, s;
int d[510][510], dir[510][510];
bool v[510][510];
multiset<pair<int, pii>> q;
int cost[200];

void vicinity(pair<int, pii> s){
vector<int> Y={-1, 1,0, 0, -1,   1, -1, 1};
vector<int> X={1, 1, 1, -1, -1, -1, 0, 0};
vector<int> D={-45, 45, 0, 180, -135, 135, -90, 90};


for(int g=0; g<D.size(); g++){
    int x=max( (int)1, min(m, s.sc.sc+X[g]) ), y=max( (int)1, min(n, s.sc.ft+Y[g]) );
    if( (v[y][x]==false) && mat[y][x]==0){
        if(dir[s.sc.ft][s.sc.sc]==-1){
            dir[y][x]=D[g];
            q.insert(mp(0, mp(y, x)) ); d[y][x]=0;
        }
        else{
            auto it=q.find(mp(d[y][x], mp(y, x)) );
            int ch=abs(D[g]-dir[s.sc.ft][s.sc.sc]);
            if(ch!=180){
                ch%=180;
            }
            int dist=d[s.sc.ft][s.sc.sc]+cost[ch];
            if(it!=q.end()){
                q.erase(it);
                if(dist<d[y][x]){
                    dir[y][x]=D[g];
                    d[y][x]=dist;
                }
            }
            else{
                d[y][x]=dist;
                dir[y][x]=D[g];
            }
            q.insert(mp(d[y][x], mp(y, x)));
        }
    }
}




}



void dijkstra(pii src){

q.insert(mp(0, src) );
v[src.ft][src.sc]=true;
dir[src.ft][src.sc]=-1;

while(!q.empty()){
pair<int, pii> f=(*q.begin()); q.erase(q.begin());
v[f.sc.ft][f.sc.sc]=true;
vicinity(f);
}




}




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];
    }
}
cost[0]=0; cost[45]=1; cost[90]=2; cost[135]=3; cost[180]=4;
dijkstra(f);
int y=s.ft; int x=s.sc;
if(v[y][x]==true && mat[y][x]==0 && mat[f.ft][f.sc]==0){
    cout<<d[y][x];
}
else{
    cout<<-1;
}

/*cout<<"\n";
for(int i=1; i<=n; i++){
    for(int j=1; j<=m; j++){
        cout<<d[i][j]<<" ";
    }
    cout<<"\n";
}*/




return 0;
}