Cod sursa(job #129198)

Utilizator DITzoneCAdrian Diaconu DITzoneC Data 28 ianuarie 2008 19:14:15
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <stdio.h>
#define nmax 502
#define ndir 8
#define DIR 7
#define Y 4088
#define X 2093056

int a[nmax][nmax], n, m, sx, sy, fx, fy, min[ndir][nmax][nmax];
int cod[nmax*nmax*ndir],Q,sf,sol=0;
int dir[ndir][2] =
  { {1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1} };
  
void adaug(int sx,int sy,int d,int ct)
{
  int i,j;
  for(i=sx,j=sy;!a[i][j];i+=dir[d][0],j+=dir[d][1])
    if(!min[d][i][j])
      {
          min[d][i][j]=ct;
	  cod[++sf]=(((i<<9)+j)<<3)+d;
	  if((i==fx)&&(j==fy))
	    sol=ct;
      }      
}

int
main ()
{
  FILE *fi = fopen ("car.in", "r"), *fo = fopen ("car.out", "w");
  int i, j, d;
  fscanf (fi, "%d %d", &n, &m);
  fscanf (fi, "%d %d %d %d", &sx, &sy, &fx, &fy);
  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++)
      fscanf (fi, "%d", &a[i][j]);
  fclose (fi);
  for(sf=-1,i=0;i<ndir;i++)
    adaug(sx,sy,i,1);
  for(Q=0;(Q<=sf)&&(!sol);Q++)
    {
       i=cod[Q]>>12;
       j=(cod[Q]&Y)>>3;
       d=cod[Q]&DIR;
       adaug(i,j,(d+1)%ndir,min[d][i][j]+1);
       adaug(i,j,(d+ndir-1)%ndir,min[d][i][j]+1);
    }
    fprintf(fo,"%d\n",sol-1);
  fclose (fo);
  return (0);
}