Cod sursa(job #1190309)

Utilizator hevelebalazshevele balazs hevelebalazs Data 24 mai 2014 23:12:21
Problema Car Scor 40
Compilator c Status done
Runda Arhiva de probleme Marime 1.51 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][9];
int Q[N*N*9],q,qs=N*N*9;
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,9)b[i][j][k]=-1;
    fr(j,0,9){
        if(j==4)continue;
        b[x1][y1][j]=0;
        Q[q++]=(m*x1+y1)*9+j;
        }
    i=0;
    while(i!=q){
        int x=Q[i];
        int d=x%9,Y=x/9,X=Y/m;
        Y=Y%m;
        int dx=d/3-1,dy=d%3-1;
        x=X+dx;
        int y=Y+dy;
        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++]=9*(m*x+y)+d;
                if(q==qs)q=0;
                }
            x+=dx;
            y+=dy;
            }
        fr(j,0,9){
            if(j==4||j==d)continue;
            int A=abs((d/3)-(j/3))+abs((j%3)-(d%3));
            if(b[X][Y][j]==-1||b[X][Y][j]>A+b[X][Y][d]){
                b[X][Y][j]=b[X][Y][d]+A;
                Q[q++]=9*(m*X+Y)+j;
                if(q==qs)q=0;
                }
            }
        if(++i==qs)i=0;
        }
    int x=-1;
    fr(k,0,9) {if(k==4) continue;if(x==-1||b[x2][y2][k]<x)x=b[x2][y2][k];}
    printf("%i",x);
    return 0;
    }