Cod sursa(job #390892)

Utilizator AndreyPAndrei Poenaru AndreyP Data 4 februarie 2010 19:09:07
Problema Car Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.6 kb
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 503
struct Nod
{
	short x,y;
	char c;
};
short n,m;
unsigned int a[N][18];
const short dx[]={-1,-1,0,1,1,1,0,-1};
const short dy[]={0,1,1,1,0,-1,-1,-1};
Nod q[N*N*8];
short sx,sy,fx,fy;
int p[10],cn[6];
int cost;
inline void set(short x,short y)
{
	a[x][y>>5]|=(1<<(y&31));
}
inline bool test(short x,short y)
{
	if((a[x][y>>5]&(1<<(y&31)))==0)
		return false;
	return true;
}
inline void citire()
{
	char c[2000]={0};
	scanf("%hd%hd",&n,&m);
        scanf("%hd%hd%hd%hd\n",&sx,&sy,&fx,&fy);

	for(short i=1; i<=n; ++i)
	{
		/*fgets(c+2,1998,stdin);
		for(short j=1; j<=m; ++j)
		{
			if(c[j<<1]=='1')
				set(i,j);
		} */
		short aux;
		for(short j=1; j<=m; ++j)
		{
			scanf("%hd",&aux);
			if(aux==1)
				set(i,j);
		}
		set(i,m+1);
		set(i,0);
	}
	memset(a[0],255,18*sizeof(unsigned int));
	memset(a[n+1],255,18*sizeof(unsigned int));
}
inline void inainte(int p,int &u)
{
	Nod next,now;
	for(int i=p; i<=u; ++i)
	{
        	now=q[i];
		next.x=now.x+dx[now.c];
		next.y=now.y+dy[now.c];
		next.c=now.c;

		if(test(next.x,next.y)==false)
		{
			if(fx==next.x && fy==next.y)
			{
				printf("%d\n",cost);
				exit(0);
			}
			set(next.x,next.y);
			q[++u]=next;
		}
	}
}
inline void vireaza(char cat,int p,int u1,int &u)
{
	Nod now,next;
	char d1,d2;
	for(; p<u1; ++p)
	{
		now=q[p];
		d1=now.c-cat;
		d2=now.c+cat;
		if(d1<0)
			d1+=8;
		if(d2>7)
			d2-=8;
		
		next.x=now.x+dx[d1];
		next.y=now.y+dy[d1];
		next.c=d1;
		if(test(next.x,next.y)==false)
		{
			if(fx==next.x && fy==next.y)
			{
				printf("%d\n",cost);
				exit(0);
			}
			set(next.x,next.y);
			q[++u]=next;
		}

		next.x=now.x+dx[d2];
		next.y=now.y+dy[d2];
		next.c=d2;
		if(test(next.x,next.y)==false)
		{
			if(fx==next.x && fy==next.y)
			{
				printf("%d\n",cost);
				exit(0);
			}
			set(next.x,next.y);
			q[++u]=next;
		}
	}
}
inline void rezolva()
{
	if(sx==fx && sy==fy)
	{
		printf("0\n");
		exit(0);
	}
	for(short i=0; i<8; ++i)
	{
		q[i].x=sx;
		q[i].y=sy;
		q[i].c=(char)i;
	}
	set(sx,sy);
	int pa=7;
	int cand=0;
	p[0]=0;
	p[1]=7;
	cn[0]=0;
	cn[1]=1;
	cn[2]=2;
	cn[3]=3;
	cn[4]=4;
	cn[5]=5;

        inainte(p[0],p[1]);

	//cost=1;
	++cost;
	p[2]=p[1];
	++p[1];
	vireaza(1,p[0],p[1],p[2]);
	inainte(p[1],p[2]);
	if(pa==p[2])
		++cand;
	else
	{
		cand=0;
		pa=p[2];
	}

	//cost=2;
	++cost;
	p[3]=p[2];
	++p[2];
	vireaza(1,p[1],p[2],p[3]);
	vireaza(2,p[0],p[1],p[3]);
	inainte(p[2],p[3]);
	if(pa==p[3])
		++cand;
	else
	{
		cand=0;
		pa=p[3];
	}

	//cost=3;
	++cost;
	p[4]=p[3];
	++p[3];
	vireaza(1,p[2],p[3],p[4]);
	vireaza(2,p[1],p[2],p[4]);
	vireaza(3,p[0],p[1],p[4]);
	inainte(p[3],p[4]);
	if(pa==p[4])
		++cand;
	else
	{
		cand=0;
		pa=p[4];
	}

	//cost=4;
	++cost;
	p[5]=p[4];
        ++p[4];
	vireaza(1,p[3],p[4],p[5]);
	vireaza(2,p[2],p[3],p[5]);
	vireaza(3,p[1],p[2],p[5]);
	vireaza(4,p[0],p[1],p[5]);
	inainte(p[4],p[5]);
	if(pa==p[5])
		++cand;
	else
	{
		cand=0;
		pa=p[5];
	}

       while(cand!=4)
       {
	      ++cost;

	      for(int i=0; i<6; ++i)
	      {
		      ++cn[i];
		      if(cn[i]==6)
			      cn[i]=0;
	      }
              	
	      p[cn[5]]=p[cn[4]];
	      ++p[cn[4]];
	      vireaza(1,p[cn[3]],p[cn[4]],p[cn[5]]);
	      vireaza(2,p[cn[2]],p[cn[3]],p[cn[5]]);
	      vireaza(3,p[cn[1]],p[cn[2]],p[cn[5]]);
	      vireaza(4,p[cn[0]],p[cn[1]],p[cn[5]]);
	      inainte(p[cn[4]],p[cn[5]]); 
	      if(p[cn[5]]==pa)
		      ++cand;
	      else
	      {
		      cand=0;
		      pa=p[cn[5]];
	      }
       }
}
int main()
{
	freopen("car.in","r",stdin);
	freopen("car.out","w",stdout);

	citire();
	rezolva();
	printf("-1\n");
	//for(int i=0; i<=u; ++i)
	//	printf("%hd %hd\n",q[i].x,q[i].y);

	return 0;
}