Cod sursa(job #1703481)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 16 mai 2016 23:47:57
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
# include <fstream>
# define DIM 505
# define INF 1000000000
# define a first.first
# define b first.second
# define c second
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
int di[]={1,1,0,-1,-1,-1,0,1};
int dj[]={0,-1,-1,-1,0,1,1,1};
pair <pair<int,int>,int> d[2][DIM*DIM*8];
int s[8][DIM][DIM],v[DIM][DIM],h[2];
int n,m,i,j,is,js,ifin,jfin,t,ic,jc,iv,jv,poz,nr,sol;
int modul(int x){
    if(x>=8)
        return x-8;
    else
        if(x<0)
            return x+8;
        else
            return x;
}
void add (int ic,int jc,int poz,int val){
    int r;
    if(ic>=1&&ic<=n&&jc>=1&&jc<=m&&v[ic][jc]==0&&s[poz][ic][jc]>val){
        r=val%2;
        d[r][++h[r]].a=ic;
        d[r][h[r]].b=jc;
        d[r][h[r]].c=poz;
        s[poz][ic][jc]=val;
    }
}
int main () {
    fin>>n>>m>>is>>js>>ifin>>jfin;
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            fin>>v[i][j];
            for(t=0;t<=7;t++)
                s[t][i][j]=INF;
        }
    }
    for(i=0;i<=7;i++)
        add(is,js,i,0);
    t=0;
    while(h[0]+h[1]>0){
        for(i=1;i<=h[t];i++){
            ic=d[t][i].a;
            jc=d[t][i].b;
            poz=d[t][i].c;
            iv=ic+di[poz];
            jv=jc+dj[poz];
            if(s[poz][ic][jc]==nr){
                add(iv,jv,poz,nr);
                poz=modul(poz-1);
                add(ic,jc,poz,nr+1);
                poz=modul(poz+2);
                add(ic,jc,poz,nr+1);
            }
        }
        h[t]=0;
        t=1-t;
        nr++;
    }
    sol=INF;
    for(i=0;i<=7;i++)
        sol=min(sol,s[i][ifin][jfin]);
    if(sol==INF){
        fout<<-1<<"\n";
        return 0;
    }
    fout<<sol<<"\n";
    return 0;
}