Cod sursa(job #1703652)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 17 mai 2016 12:43:43
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
# include <fstream>
# include <cstring>
# define DIM 505
# define INF 0x3f3f3f3f
# 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[DIM][DIM][8],v[DIM][DIM],h[2];
int n,m,i,j,is,js,ifin,jfin,t,ic,jc,iv,jv,poz,nr,sol;
inline 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[ic][jc][poz]>val){
        r=val&1;
        d[r][++h[r]].a=ic;
        d[r][h[r]].b=jc;
        d[r][h[r]].c=poz;
        s[ic][jc][poz]=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];
        }
    }
    memset(s,INF,sizeof(s));
    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[ic][jc][poz]==nr){
                add(iv,jv,poz,nr);
                poz=(poz+23)&7;
                add(ic,jc,poz,nr+1);
                poz=(poz+26)&7;
                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[ifin][jfin][i]);
    if(sol==INF){
        fout<<-1<<"\n";
        return 0;
    }
    fout<<sol<<"\n";
    return 0;
}