Cod sursa(job #1703498)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 17 mai 2016 00:12:07
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
# include <fstream>
# include <cstdio>
# define DIM 505
# define INF 1000000000
# define a first.first
# define b first.second
# define c second
using namespace std;
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){
        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 () {
    freopen("car.in","r",stdin);
    freopen("car.out","w",stdout);
    scanf("%d%d%d%d%d%d\n",&n,&m,&is,&js,&ifin,&jfin);
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            scanf("%d\n",&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,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,t);
                poz=modul(poz-1);
                add(ic,jc,poz,nr+1,1-t);
                poz=modul(poz+2);
                add(ic,jc,poz,nr+1,1-t);
            }
        }
        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){
        printf("-1\n");
        return 0;
    }
    printf("%d\n",sol);
    return 0;
}