Cod sursa(job #20830)

Utilizator m_dersidanDersidan Mihai m_dersidan Data 22 februarie 2007 13:02:09
Problema Car Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 4 kb
# include <stdio.h>
# include <string.h>

# define  _fin  "car.in"
# define  _fout "car.out"

# define  maxn  502
# define  maxd  9

# define  maxb  1<<21

# define  inf	25000002


typedef struct nod
{
	int  flag;
	nod *next;
}	*pnod;

/* implement non-pointer based lists */
int l[3][250000];	// lists
int lh[3], le[3];	// list head / end
//

int dy[] = { -1,-1, 0, 1, 1, 1, 0,-1 }, dx[] = {  0,-1,-1,-1, 0, 1, 1, 1 };


int d[maxb];// , viz[maxb];
int v[maxn][maxn][maxd];

int n, m, sol;	// lista curenta, lista maxima
int is, js, ie, je;

// pnod l[3], crt;		//
int  act, crt;			// lista / pozitia in ea


inline int  ison(int i, int j) 				{ return (i>=1&&i<=n) && (j>=1&&j<=m); }
inline int  ttf(int x) 						{ return (x+4)%8; }		// translate to->from


inline void setflags(int &a, int dx, int dy, int dir)
{
	a = ( dx << 9 ) + dy + ( dir << 18 );
}

inline int setflags(int dx, int dy, int dir)
{
	return ( dx << 9 ) + dy + ( dir << 18 );
}

inline void getflags(int a, int &dx, int &dy, int &dir)
{
	dir = a >> 18, dy = a & 511, dx = ( a >> 9 ) & 511;
}

void insert(int a, int dist)
{
/*	if ( !l[ dist ] )
		l[ dist ] = new nod, l[ dist ] -> next = NULL,
		l[ dist ] -> flag = a;//, l[ dist ]->used = 1;
	
	else
	{
		pnod q, last;
		for (q=new nod, last=l[ dist ]; last->next; last = last->next);
		q -> flag = a, q -> next = NULL, last -> next = q; // q -> used = 1, 
	}

	viz[ a ] = 1;*/
//	if ( !le[ dist ] )
//		++le[ dist ];
//	l[ dist ][ ++lh[dist] ] = dist;
	l[ dist ][ ++le[ dist ] ] = a;
}

int looplist()
{
	/*
	crt = crt->next;

	if ( !crt )
	{
		pnod q;
		while ( l[ act%3 ] )
			q = l[ act%3 ], l[ act%3 ] = l[ act%3 ] -> next, delete q;
		
		if ( !l[ (act+1)%3 ] && !l[ (act+2)%3 ] ) return 0;		// over
		
		while ( !crt )
			crt = l[ (++act) % 3 ];
	}

	return 1;*/
	++crt;
	
	if ( crt > le[ act%3 ] )
	{
		// delete old list
		le[ act % 3 ] = 0; // lh[ act % 3 ] = 
		
		if ( !le[ (act+1) % 3 ] && !le[ (act+2) % 3 ] ) return 0;	// end
		
		while ( !le[ act%3 ] ) ++act;
		
		crt = 1;						// start of list
	}
	
	return 1;
}

int a[maxn][maxn];

void readf()
{
	freopen(_fin, "r", stdin);
	int i, j, k;
	
	scanf("%d%d", &n, &m);
	scanf("%d%d%d%d", &is, &js, &ie, &je);
	
	for (i=1; i<=n; i++)
		for (j=1; j<=m; j++) scanf("%d", &a[i][j]);
	
	for (i=1; i<=n; i++)
		for (j=1; j<=m; j++)
			if ( !a[i][j] )
			for (k=0; k<8; k++)
				if ( ison(i+dx[k], j+dy[k]) )
					if ( !a[i+dx[k]][j+dy[k]] )
						v[ i ][ j ][ k ] = 1;	// se poate merge in directia k
}

int dir2[maxd][maxd], costs[maxd];

void solve()
{
	int i;
	int cx, cy, cdir, cflag, rez, aux, newd;
	
	for (i=0; i<maxb; i++) d[i] = inf;
	
	for (i=0; i<8; i++)
		if ( v[ is ][ js ][ i ]==1 )
			insert( aux=setflags(is+dx[i],js+dy[i],ttf(i)), 0 ), d[aux]=0;

	crt = 1, act = 0;
	costs[1]=0, costs[2]=costs[3]=1, costs[4]=costs[5]=2;

	for (cdir=0; cdir<8; cdir++)
		dir2[cdir][1] = (cdir+4) % 8, dir2[cdir][2] = (cdir+3) % 8, dir2[cdir][3] = (cdir+5) % 8, dir2[cdir][4] = (cdir+2) % 8, dir2[cdir][5] = (cdir+6) % 8;

	while ( 1 )
	{
		cflag = l[ act%3 ][ crt ]; // crt->flag;
		cdir = cflag >> 18,
		cy = cflag & 511,
		cx = ( cflag >> 9 ) & 511;
		
		for (i=1; i<=5; i++)
			if ( v[ cx ][ cy ][ dir2[cdir][i] ] )
			{
				aux = setflags(cx+dx[dir2[cdir][i]], cy+dy[dir2[cdir][i]], ttf(dir2[cdir][i]) );
				
				if ( costs[i] + d[cflag] < d[aux] )
				{
					// if ( viz[ aux ] ) del( aux, d[a] % 3 );
					insert(aux, (newd=(costs[i]+d[cflag])) % 3), d[aux] = newd;
				}
			}

		rez=looplist();
		
		while ( rez && act > d[ l[ act%3 ][ crt ] ] ) rez=looplist(); // !viz[crt->flag]
		// while ( rez && crt->used == 0 ) rez=looplist();
		
		if ( !rez ) break;
	}

	for (sol = inf, i=0; i<8; i++)
		if ( d[ setflags(ie, je, i)] < sol ) sol = d[ setflags(ie, je, i) ];
}

void writef()
{
	freopen(_fout, "w", stdout);
	printf("%d\n", sol==inf?-1:sol);
}

int main()
{
	readf();
	solve();
	writef();
	
	return 0;
}