Cod sursa(job #2166780)

Utilizator catalinlupCatalin Lupau catalinlup Data 13 martie 2018 18:53:51
Problema Car Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <bits/stdc++.h>
#define INFILE "car.in"
#define OUTFILE "car.out"
#define x first
#define y second
#define lung first
#define mod second.first
#define poz second.second
using namespace std;
const int NMAX=510;
typedef array<array<int,NMAX>,NMAX> Map;
typedef pair<int,int> coord;
ifstream in(INFILE);
ofstream out(OUTFILE);
const int nrdir=8;
const int INF=INT_MAX;
int dlin[nrdir+1]={0,-1,-1,0,1,1,1,0,-1};
int dcol[nrdir+1]={0,0,1,1,1,0,-1,-1,-1};
int Cost(int reper,int dir){
    int val=abs(reper-dir);
    if(val>nrdir/2)
        return nrdir-val;
    return val;
}
array<Map,nrdir+1> dist;
Map Harta;
int N,M;
int Si,Sj,Fi,Fj;
void AfisMp(Map&mp){
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            if(mp[i][j]==INF){
                cout<<setw(2)<<-1<<" ";
            }
            else cout<<setw(2)<<mp[i][j]<<" ";
        }
        cout<<"\n";
    }
    cout<<"~~~\n";
}


void Read(){
    in>>N>>M;

    in>>Si>>Sj>>Fi>>Fj;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            in>>Harta[i][j];
        }
    }
    //cout<<N<<" "<<M<<endl;
    //AfisMp(Harta);

}

bool OutOfBoundries(int lin,int col){
    if(lin<1||col<1||lin>N||col>M)
        return true;
    if(Harta[lin][col]==1)
        return true;
    return false;
}



void Dijkstra(){
    typedef pair<int,pair<int,coord>> superData;
    priority_queue<superData,vector<superData>,greater<superData>> coada;
    for(int k=1;k<=nrdir;k++){
        coada.push({0,{k,{Si,Sj}}});
        for(int i=1;i<=N;i++){
            for(int j=1;j<=M;j++){
                dist[k][i][j]=INF;
            }
        }
        dist[k][Si][Sj]=0;
    }
    while(!coada.empty()){
        int lin=coada.top().poz.x;
        int col=coada.top().poz.y;
        int reper=coada.top().mod;
        int dst=coada.top().lung;
        coada.pop();
        for(int k=1;k<=nrdir;k++){
            int nlin=lin+dlin[k];
            int ncol=col+dcol[k];
            //cout<<nlin<<" "<<ncol<<" "<<k<<"\n";
            if(OutOfBoundries(nlin,ncol)) continue;

            int cost=Cost(reper,k);
            if(dist[k][nlin][ncol]>dst+cost){
                dist[k][nlin][ncol]=dst+cost;
                //
                //cout<<dist[k][nlin][ncol]<<" "<<k<<" "<<nlin<<" "<<ncol<<"\n";
                coada.push({dst+cost,{k,{nlin,ncol}}});
            }
        }
    }
    int Mn=INF;

    for(int k=1;k<=nrdir;k++){
        //AfisMp(dist[k]);
        Mn=min(Mn,dist[k][Fi][Fj]);
    }
    if(Mn==INF){
        out<<-1<<"\n";
    }
    else{
        out<<Mn;
    }

}

int main(){
    Read();
    Dijkstra();
    return 0;
}