Cod sursa(job #1190356)

Utilizator hevelebalazshevele balazs hevelebalazs Data 25 mai 2014 09:43:54
Problema Car Scor 70
Compilator c Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <stdio.h>
#define fr(i,a,b) for(i=a;i<b;++i)
#define N 500
int a[N][N];
int b[N][N][8];
int Q[N*N*8],q,qs=N*N*8;
int dx[]={-1,-1,-1,0,1,1,1,0};
int dy[]={-1,0,1,1,1,0,-1,-1};
inline int abs(int a){return a>0?a:-a;}
int main(){
    freopen("car.in","r",stdin);
    freopen("car.out","w",stdout);
    int n,m;
    scanf("%i%i",&n,&m);
    int x1,y1,x2,y2;
    scanf("%i%i%i%i",&x1,&y1,&x2,&y2);
    --x1,--y1,--x2,--y2;
    int i,j,k;
    fr(i,0,n)fr(j,0,m)scanf("%i",a[i]+j);
    fr(i,0,n)fr(j,0,m)fr(k,0,8)b[i][j][k]=-1;
    fr(j,0,8){
        b[x1][y1][j]=0;
        Q[q++]=(m*x1+y1)*8+j;
        }
    i=0;
    while(i!=q){
        int x=Q[i];
        int d=x%8,Y=x/8,X=Y/m;
        Y=Y%m;
        x=X+dx[d];
        int y=Y+dy[d];
        while(x>=0 && x<n && y>=0 && y<m  && !a[x][y]){
            if(b[x][y][d]==-1 || b[x][y][d]>b[X][Y][d]){
                b[x][y][d]=b[X][Y][d];
                Q[q++]=8*(m*x+y)+d;
                if(q==qs)q=0;
                }
            x+=dx[d];
            y+=dy[d];
            }
        fr(j,0,2){
            int k=(d+(j?7:1))%8;
            if(b[X][Y][k]==-1||b[X][Y][k]>1+b[X][Y][d]){
                b[X][Y][k]=b[X][Y][d]+1;
                Q[q++]=8*(m*X+Y)+k;
                if(q==qs)q=0;
                }
            }
        if(++i==qs)i=0;
        }
    int x=-1;
    fr(k,0,8) if(x==-1||b[x2][y2][k]<x)x=b[x2][y2][k];
    printf("%i",x);
    return 0;
    }