Cod sursa(job #44062)

Utilizator m_dersidanDersidan Mihai m_dersidan Data 30 martie 2007 20:49:56
Problema Car Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.79 kb
# include <stdio.h>
# include <string.h>

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

# define  maxn  501
# define  maxd  8

# define  maxb  1<<21
# define  maxmd 30000

# define  inf	25000002


int dy[] = { -1,-1, 0, 1, 1, 1, 0,-1 }, dx[] = {  0,-1,-1,-1, 0, 1, 1, 1 }, ttf[] = { 4, 5, 6, 7, 0, 1, 2, 3 };


int d[maxb];
char v[maxn][maxn][maxd], a[maxn][maxn],
	m3[maxmd];

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

int l[3][250003];		// lists
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  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; }


int looplist()
{
	++crt;
	
	if ( crt > l[ m3[act] ][ 0 ] )
	{
		l[ m3[act] ][0] = 0;
		if ( !l[ m3[act+1] ][0] && !l[ m3[(act+2)] ][0] ) return 0;
		while ( !l[ m3[act] ][0] ) ++act; crt = 1;
	}
	
	return 1;
}

void readf()
{
	freopen(_fin, "r", stdin);
	int i, j, k, x;
	
	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", &x), a[i][j] = x;
	
	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, cx, cy, cdir, cflag, rez, aux, newd;
	
	for (i=0; i<maxb; i++) d[i] = inf;
	for (i=0; i<maxmd; i++) m3[i] = i%3;
	
	for (i=0; i<8; i++)
		if ( v[ is ][ js ][ i ]==1 )
			d[ l[0][ ++l[0][0] ] = setflags(is+dx[i],js+dy[i],ttf[i]) ] = 0;

	crt = 1; 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[ m3[act] ][ crt ];
		cdir = cflag >> 18, cy = cflag & 511, cx = ( cflag >> 9 ) & 511;
		
		for (i=1; i<=5; i++)
			if ( v[ cx ][ cy ][ dir2[cdir][i] ] )
				if ( costs[i] + d[cflag] < d[aux = setflags(cx+dx[dir2[cdir][i]], cy+dy[dir2[cdir][i]], ttf[dir2[cdir][i]] )] )
					d[ l[ (newd=(costs[i]+d[cflag])) % 3 ][ ++l[ m3[newd] ][0] ] = aux ] = newd;

		rez=looplist();
		
		while ( rez && act > d[ l[ m3[act] ][ crt ] ] ) rez=looplist(); // !viz[crt->flag]
		
		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;
}