Cod sursa(job #443807)

Utilizator mgntMarius B mgnt Data 18 aprilie 2010 15:00:23
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <iostream>
#include <fstream>
using namespace std;

int const maxc = 501+(501<<9)+(7<<18);

// d, sol <- 0 ( program loader )

int
 dx[]={-1,-1,0,1,1,1,0,-1},
 dy[]={0,1,1,1,0,-1,-1,-1},
 a[502][502],
 d[1+maxc], q[1+maxc], iq, eq,
 n,m,sx,sy,fx,fy,sol;

void add(int ax, int ay, int az, int ct)
{
  int x, y, t;
  for(x=ax, y=ay; !a[x][y]; x+=dx[az], y+=dy[az])
  {
    t=x+(y<<9)+(az<<18);
    if(!d[t])
    {
      if ((fx ==x)&&(fy==y))
      { sol = ct; return; }
      d[t]=ct; q[eq++]=t;
    }
  }
}

int main()
{
  ifstream is("car.in");
  is >> n >> m
     >> sx >> sy >> fx >> fy;
  int x, y, z, t;
  for(x=0; n+1>=x; ++x)
    for(y=0; m+1>=y; ++y)
      a[x][y]=1;
  for(x=1; n>=x; ++x)
    for(y=1; m>=y; ++y)
       is >> a[x][y];
  eq=0; iq=0;
  for(z=0; 8>z; ++z) { add(sx,sy,z,1); }
  for ( iq=0; !sol && (iq<eq); ++iq )
  {
    t=q[iq]; x=t&511; y=(t>>9)&511; z=t>>18;
    add(x,y,(1+z)%8,d[t]+1);
    add(x,y,(7+z)%8,d[t]+1);
  }
  ofstream os("car.out");
  os << sol-1 << endl;
  return 0;
}