Cod sursa(job #134521)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 11 februarie 2008 20:25:26
Problema Car Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include <stdio.h>
#include <math.h>
#include <iostream.h>
#define stiva 2500000
#define inf 2000000000
#define nmax 502

long min(long a,long b){
     if (a<b)return a;
     //return a<b?a:b;
     return b;
}

long n,m,i,j,k,p,q,li,ci,lf,cf;
long x[stiva],y[stiva],xx,yy,c;
long cost[nmax][nmax],poz[nmax][nmax];
bool a[nmax][nmax];
long dx[]={0,-1,-1,0,1,1,1,0,-1};
long dy[]={0,0,1,1,1,0,-1,-1,-1};

int main(){
    freopen("car.in","r",stdin);
    freopen("car.out","w",stdout);
    
    scanf("%ld %ld",&n,&m);
    scanf("%ld %ld %ld %ld",&li,&ci,&lf,&cf);
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++){
            scanf("%ld",&a[i][j]);
            cost[i][j]=inf;
        }
    
    p=2;q=1;
    poz[li][ci]=0;
    cost[li][ci]=-1;
    x[1]=li;y[1]=ci;
    
    for (k=1;k<=8;k++){
        xx=li+dx[k];
        yy=ci+dy[k];
        if (xx>0&&xx<=n&&yy>0&&yy<=m)
           if (!a[xx][yy]){
              q++;
              x[q]=xx;y[q]=yy;
              cost[xx][yy]=0;
              poz[xx][yy]=k;
              
           }
    }
    
    while (p<=q){
          for (k=1;k<=8;k++){
              xx=x[p]+dx[k];
              yy=y[p]+dy[k];
              if (xx>0&&xx<=n&&yy>0&&yy<=m)
                 if (!a[xx][yy]){
                    c=abs(poz[x[p]][y[p]]-k);
                    c=min(c,8-c);
//                    printf("%ld\n",c);
                    if (cost[x[p]][y[p]]+c<cost[xx][yy]){
                       q++;
                       x[q]=xx;y[q]=yy;
                       cost[xx][yy]=cost[x[p]][y[p]]+c;
                       poz[xx][yy]=k;
                       //if (poz[xx][yy]>8)poz[xx][yy]-=8;
                    }
                 }
              
          }
          p++;
    }
//    for (i=1;i<=n;i++){
//        for (j=1;j<=m;j++)
//            printf("%ld ",cost[i][j]);
//        printf("\n");
//    }
    if (cost[lf][cf]!=inf)
       printf("%ld\n",cost[lf][cf]);
    else
        printf("-1\n");

return 0;    
}