Cod sursa(job #308905)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 28 aprilie 2009 20:42:26
Problema Car Scor 100
Compilator cpp Status done
Runda tot Marime 1.65 kb
#include <stdio.h>   
#include <queue>   
#include <bitset>   
#define INF 32000   
using namespace std;   
struct st{short int x,y,d;};   
short int c[501][501][8];   
char ch[1024]; bitset <512> a[501];   
queue <st>Q;   
  
inline short int cc(short int x,short int y){   
 short int aux,f1,f2;   
 if (x>y){aux=x;x=y;y=aux;}   
 f1=x+8-y;f2=y-x;   
 if (f1<f2)return f1; else return f2;   
}   
int main(){   
  freopen("car.in","r",stdin); freopen("car.out","w",stdout);   
  /**/   
  register short int n,m,x1,y1,x2,y2,i,j,k,x,y,d,xx,yy,sol,*nod,*fiu,cst[8][8];   
  register short int dx[]={-1,-1,0,1,1,1,0,-1},dy[]={0,1,1,1,0,-1,-1,-1};   
  register st aux;   
  for (i=0;i<8;++i)for (j=0;j<8;++j)cst[i][j]=cc(i,j);   
  /**/   
  scanf("%hd %hd %hd %hd %hd %hd\n",&n,&m,&x1,&y1,&x2,&y2);   
  for (i=1;i<=n;++i){   
    gets(ch);   
    for (j=0;j<(m+m);j+=2)a[i][j/2+1]=ch[j]-'0';   
  }   
  for (i=1;i<=n;++i)for (j=1;j<=m;++j)for (k=0;k<8;++k)c[i][j][k]=INF;   
  for (i=0;i<8;++i){c[x1][y1][i]=0;aux.x=x1;aux.y=y1;aux.d=i;Q.push(aux);}   
  sol=INF;   
  while (!Q.empty()){   
   aux=Q.front();Q.pop();x=aux.x;y=aux.y;d=aux.d;   
   nod=&c[x][y][d];   
   for (i=0;i<8;++i){   
     if (cst[d][i]>2)continue;   
     xx=x+dx[i];yy=y+dy[i]; fiu=&c[xx][yy][i];   
     if (xx>0&&xx<=n&&yy>0&&yy<=m)   
      if (!a[xx][yy])   
       if ( *nod + cst[d][i] < *fiu ){   
         *fiu= *nod + cst[d][i];   
         if (*fiu < sol){aux.x=xx;aux.y=yy;aux.d=i;Q.push(aux);}   
         if (c[x2][y2][i]<sol)sol=c[x2][y2][i];   
       }   
   }   
  }   
  if (sol!=INF)printf("%d\n",sol);else printf("-1\n");   
return 0;   
}