Cod sursa(job #256395)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 11 februarie 2009 18:50:31
Problema Car Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 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,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);}
  while (!Q.empty()){
   aux=Q.front();Q.pop();x=aux.x;y=aux.y;d=aux.d;
   for (i=0;i<8;++i){
     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] + cst(d,i) < c[xx][yy][i] ){
         c[xx][yy][i]=c[x][y][d] + cst(d,i);
         aux.x=xx;aux.y=yy;aux.d=i;Q.push(aux);
       }
   }
  }
  j=INF;
  for (i=0;i<8;++i)if (c[x2][y2][i]<j)j=c[x2][y2][i];
  printf("%d\n",j);
return 0;
}