Cod sursa(job #256436)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 11 februarie 2009 19:07:24
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <stdio.h>
#include <queue>
#define INF 32000
using namespace std;
struct st{short int x,y,d;}aux;
short int n,m,x1,y1,x2,y2,i,j,k,x,y,d,xx,yy,sol,cc,c[501][512][8];
char ch[1024]; char a[501][512];
short int dx[]={-1,-1,0,1,1,1,0,-1},dy[]={0,1,1,1,0,-1,-1,-1};
queue <st>Q;

short int cst(short int x,short int y){
  if (x>y)x=x+y-(y=x);
  if (x+8-y<y-x)return (x+8-y); else return (y-x);
}
int main(){
  freopen("car.in","r",stdin); freopen("car.out","w",stdout);
  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;
   for (i=0;i<8;++i){
     cc=cst(d,i);
     if (cc>2)continue;
     xx=x+dx[i];yy=y+dy[i];
     if (xx>0&&xx<=n&&yy>0&&yy<=m)
       if (a[xx][yy]==0)
       if ( c[x][y][d] + cc < c[xx][yy][i] ){
         c[xx][yy][i]=c[x][y][d] + cc;
         if (c[xx][yy][i]<sol){aux.x=xx;aux.y=yy;aux.d=i;Q.push(aux);}
         if (xx==x2&&yy==y2)if (c[xx][yy][i]<sol)sol=c[xx][yy][i];
       }
   }
  }
  /*j=INF;
  for (i=0;i<8;++i)if (c[x2][y2][i]<j)j=c[x2][y2][i];*/
  if (sol!=INF)printf("%d\n",sol);else printf("-1\n");
return 0;
}