Cod sursa(job #1528008)

Utilizator livliviLivia Magureanu livlivi Data 18 noiembrie 2015 22:34:29
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include<cstdio>
#define N 500
#define D 8
#define MULT N*N*D
using namespace std;

bool in[N+1][N+1];
int d[N+1][N+1][D];
int dep[D][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
int dq[MULT];

int n,m;

int schimba(int a,int x){
    a=a+x;
    if (a<0) a+=MULT;
    else a-=MULT;
    if (a<0) a+=MULT;
    return a;
}

void parc(int lin,int col){
    int i,st,dr,a,b,c,na,nb,nc;

    for(i=0;i<D;i++){
        d[lin][col][i]=1;
        dq[i]=(lin<<13)+(col<<4)+i;
    }

    st=0;
    dr=D;
    while(st<dr){
        a=(dq[st]>>13);
        b=((dq[st]>>4)&((1<<9)-1));
        c=(dq[st]&((1<<4)-1));
        st=schimba(st,1);

        na=a+dep[c][0];
        nb=b+dep[c][1];
        if (na>0 &&nb>0 &&na<=n &&nb<=m &&in[na][nb]==0 &&(d[na][nb][c]==0 ||d[na][nb][c]>d[a][b][c])){
            d[na][nb][c]=d[a][b][c];
            st=schimba(st,-1);
            dq[st]=(na<<13)+(nb<<4)+c;
        }

        nc=c+1-D;
        if (nc<0) nc+=D;

        if (d[a][b][nc]==0 ||d[a][b][nc]>d[a][b][c]+1){
            d[a][b][nc]=d[a][b][c]+1;
            dq[dr]=(a<<13)+(b<<4)+nc;
            dr=schimba(dr,1);
        }

        nc=c-1;
        if (nc<0) nc+=D;

        if (d[a][b][nc]==0 ||d[a][b][nc]>d[a][b][c]+1){
            d[a][b][nc]=d[a][b][c]+1;
            dq[dr]=(a<<13)+(b<<4)+nc;
            dr=schimba(dr,1);
        }
    }
}


int main(){
    freopen ("car.in","r",stdin);
    freopen ("car.out","w",stdout);
    int i,j,sl,sc,fl,fc;
    int min;

    scanf ("%d%d%d%d%d%d",&n,&m,&sl,&sc,&fl,&fc);

    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            scanf ("%d",&in[i][j]);

    parc(sl,sc);

    min=0;
    for(i=0;i<D;i++)
        if (min==0 ||d[fl][fc][i]<min) min=d[fl][fc][i];

    printf ("%d",min-1);
    return 0;
}