Cod sursa(job #285880)

Utilizator lolopolololopolo lolopolo Data 23 martie 2009 09:10:01
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 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;
}