Cod sursa(job #1493843)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 29 septembrie 2015 23:10:30
Problema Car Scor 80
Compilator c Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <stdio.h>
#define INF 1000000000
#define MAXN 500
#define MAXK (5*MAXN*MAXN+1)
#define MAXD (2*MAXN*MAXN)
#define NRDIR 8
int dl[NRDIR]=
{
    -1, -1, 0, 1, 1, 1, 0, -1
};
int dc[NRDIR]=
{
    0, 1, 1, 1, 0, -1, -1, -1
};
int k;
int q[MAXN+2][MAXN+2], ok[1<<21], d[MAXN+1][MAXN+1][NRDIR], e[MAXK+1], l[MAXD+1], s[MAXD+1], urm[MAXK+1];
inline int myabs(int a){
    if(a<0){
        return -a;
    }
    return a;
}
inline void adauga(int a, int b, int c, int o){
    k++;
    e[k]=o+(c<<3)+(b<<12);
    d[b][c][o]=a;
    if(l[a]==0){
        l[a]=s[a]=k;
    }else{
        urm[s[a]]=k;
        s[a]=k;
    }
}
int main(){
    int n, m, x1, y1, x2, y2, i, j, t, ans, x, y, r, a, b;
    FILE *fin, *fout;
    fin=fopen("car.in", "r");
    fout=fopen("car.out", "w");
    fscanf(fin, "%d%d%d%d%d%d ", &n, &m, &x1, &y1, &x2, &y2);
    for(i=1; i<=n; i++){
        for(j=1; j<=m; j++){
            fscanf(fin, "%d", &q[i][j]);
            for(t=0; t<NRDIR; t++){
                d[i][j][t]=INF;
            }
        }
    }
    for(i=0; i<=n+1; i++){
        q[i][0]=q[i][m+1]=1;
    }
    for(i=0; i<=m+1; i++){
        q[0][i]=q[n+1][i]=1;
    }
    for(i=0; i<NRDIR; i++){
        if(q[x1+dl[i]][y1+dc[i]]==0){
            adauga(0, x1+dl[i], y1+dc[i], i);
        }
    }
    t=0;
    while(t<=MAXD){
        while((t<=MAXD)&&(l[t]==0)){
            t++;
        }
        if(t<=MAXD){
            if(ok[e[l[t]]]==0){
                ok[e[l[t]]]=1;
                x=e[l[t]]>>12;
                y=(e[l[t]]>>3)&511;
                r=e[l[t]]&7;
                for(j=r-2; j<=r+2; j++){
                    i=(j+8)&7;
                    a=x+dl[i];
                    b=y+dc[i];
                    if((q[a][b]==0)&&(ok[(a<<12)+(b<<3)+i]==0)&&(d[a][b][i]>d[x][y][r]+myabs(r-j))){
                        adauga(d[x][y][r]+myabs(r-j), a, b, i);
                    }
                }
            }
            l[t]=urm[l[t]];
        }
    }
    ans=INF;
    for(i=0; i<NRDIR; i++){
        if(ans>d[x2][y2][i]){
            ans=d[x2][y2][i];
        }
    }
    if(ans==INF){
        ans=-1;
    }
    fprintf(fout, "%d\n", ans);
    fclose(fin);
    fclose(fout);
    return 0;
}