Cod sursa(job #84749)

Utilizator VmanDuta Vlad Vman Data 16 septembrie 2007 19:01:13
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.56 kb
#include <stdio.h>
#include <vector>
using namespace std;

#define Nmax 500
#define Mmax 500
#define Xmax 1 << 21 + 1

int N,M,i,j,cost = 0;
int Sx,Sy,Fx,Fy;
int a[Nmax][Mmax];
int d[Xmax];
int xx[8]={-1,-1,0,1,1,1,0,-1};
int yy[8]={0,-1,-1,-1,0,1,1,1};
vector<int> c[2];

void citire()
{
 freopen("car.in","r",stdin);
 scanf("%d %d",&N,&M);
 scanf("%d %d %d %d",&Sx,&Sy,&Fx,&Fy);
 --Sx;--Sy;--Fx;--Fy;
 for (i=0;i<N;++i)
     for (j=0;j<N;++j)
         scanf("%d",&a[i][j]);
 fclose(stdin);
}

int expand(int nod)
{
  int px,py,dir,aux;
  //despachetarea
  dir = nod >> 18;
  px = (nod >> 9) - (dir << 9) + xx[dir];
  py = nod - (dir << 18) - ((px-xx[dir]) << 9) + yy[dir];
      // 45 grade la dreapta
      if (dir == 0)
          if (d[ nod + (7 << 18) ] > d[ nod ] + 1)
             {
              c[1-(cost & 1)].push_back( nod + (7 << 18) );
              d[ nod + (7 << 18) ] = d[ nod ] + 1;
             }
             else;
        else
          if (d[ nod - (1 << 18) ] > d[ nod ] + 1)
             {
              c[1-(cost & 1)].push_back( nod - (1 << 18) );
              d[ nod - (1 << 18) ] = d[ nod ] + 1;
             }
      //45 grade la stanga
      if (dir == 7)
          if (d[ nod - (7 << 18) ] > d[ nod ] + 1)
             {
              c[1-(cost & 1)].push_back( nod - (7 << 18) );
              d[ nod - (7 << 18) ] = d[ nod ] + 1;
             }
             else;
        else
          if (d[ nod + (1 << 18) ] > d[ nod ] + 1)
             {
              c[1-(cost & 1)].push_back( nod + (1 << 18) );
              d[ nod + (1 << 18) ] = d[ nod ] + 1;
             }
  if ((px < 0) || (py < 0) || (px>=N) || (py>=M)) return 0;
     else if ((px == Fx) && (py == Fy)) return 2;
  //nodul din directia de mers
  aux = (dir << 18) + (px << 9) + py;
  if ((d[ aux ] > d[ nod ]) && (a[px][py] == 0))
     {
      //drept inainte
      c[cost & 1].push_back( aux );
      d[ aux ] = d[ nod ];
     }
return 1;
}

int dijkstra()
{
 int P=(Sx << 9) + Sy;
 int x, v, r;
 memset(d,0x3f,sizeof(d));
 for (i=0; i<8; ++i)
     {
      c[0].push_back( (i << 18) + P );
      d[ (i << 18) + P ] = 0;
     }
 while ( c[0].size()+c[1].size() )
       {
        r = cost & 1;
        while ( c[r].size() )
           {
            x = c[r][ c[r].size() - 1 ];
            c[r].pop_back();
            if (expand(x) == 2) return cost;
           }
        ++cost;
       }
return -1;
}

int main()
{
 citire();
 freopen("car.out","w",stdout);
 printf("%d",dijkstra());
 fclose(stdout);
 return 0;
}