Cod sursa(job #253207)

Utilizator 630r63Ilinca George Mihai 630r63 Data 5 februarie 2009 15:54:56
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.13 kb
 #include <stdio.h>  
 #include <vector>  
   
 using namespace std;  
   
 #define maxl 510  
 #define maxval 500010  
   
 int n,m,i,j,k,l,p,q,dir,newX,newY;  
 int a[maxl][maxl];  
 int x[5],y[5];  
 int d1[8]={0,-1,-1,-1,0,1,1,1};  
 int d2[8]={1,1,0,-1,-1,-1,0,1};  
 int cost[8][8];  
 int val[maxl][maxl][8];  
 vector <int> c[maxval];  
   
 void expand()  
 {  
     for (j=0; j<8; j++)  
     {  
         newX=p+d1[j];newY=q+d2[j];  
         if (!a[newX][newY] &&  
             (val[newX][newY][j]<0 || val[p][q][dir]+cost[dir][j]<val[newX][newY][j]))  
         {  
             val[newX][newY][j]=val[p][q][dir]+cost[j][dir];  
             c[i+cost[j][dir]].push_back((newX<<9)+newY+(j<<18));  
         }  
     }  
 }  
   
 int main()  
 {  
     freopen("car.in","r",stdin);  
     freopen("car.out","w",stdout);  
   
     scanf("%d %d",&n,&m);  
     scanf("%d %d %d %d",&x[1],&y[1],&x[2],&y[2]);  
   
     for (i=0; i<=n+1; i++)  
         for (j=0; j<=m+1; j++)  
             a[i][j]=1;  
     for (i=1; i<=n; i++)  
         for (j=1; j<=m; j++)  
             scanf("%d",&a[i][j]);  
     for (i=1; i<=n; i++)  
         for (j=1; j<=m; j++)  
             for (k=0; k<8; k++) val[i][j][k]=-1;  
   
     for (i=0; i<8; i++)  
         for (j=0; j<i; j++)  
         {  
             k=i-j;  
             if (k>4) k=cost[i-1][j]-1;  
             cost[i][j]=k;  
             cost[8-i-1][8-j-1]=k;  
         }  
           
     for (i=0; i<=7; i++)  
     {  
         c[0].push_back((x[1]<<9)+y[1]+(i<<18));  
         val[x[1]][y[1]][i]=0;  
     }  
   
     for (i=0; i<=maxval; i++)  
         while (c[i].size()>0)  
         {  
             l=c[i].size()-1;  
             k=c[i][l];  
             c[i].pop_back();  
               
             dir=k>>18;  
             q=k&511;  
             p=(k>>9)&511;  
               
             if (p==x[2] && q==y[2])  
             {  
                 printf("%d\n",i);  
                 return 0;  
             }  
   
             expand();  
         }  
   
     printf("-1\n");  
     return 0;  
}