Cod sursa(job #20794)

Utilizator m_dersidanDersidan Mihai m_dersidan Data 22 februarie 2007 12:17:57
Problema Car Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.33 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;
	char used;

	nod *next;
}	*pnod;


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;		// lista curenta


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 -> used = 1, q -> next = NULL, last -> next = q;
	}

	viz[ a ] = 1;
}

void del(int a, int dist)
{
	pnod i;
	
	for (i=l[dist]; i->flag != a; i=i->next);
	if ( i ) i->used = 0;	// should not if
}

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

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

	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
}

void expand(int a, int newd)
{
	if ( newd >= d[ a ] ) return;

	if ( viz[ a ] ) del( a, d[a] % 3 );
	insert(a, newd % 3); d[ a ] = newd;
}

void solve()
{
	int i, dirs[maxd], costs[maxd];
	int cx, cy, cdir, cflag, rez;
	
	for (i=0; i<maxb; i++) d[i] = inf;
	
	for (i=0; i<8; i++)
		if ( v[ is ][ js ][ i ]==1 )
			expand( setflags(is,js,ttf(i)), 0 );

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

	while ( 1 )
	{
		getflags(crt->flag, cx, cy, cdir);
		cflag = crt->flag;
		
		dirs[1] = (cdir+4) % 8, dirs[2] = (cdir+3) % 8, dirs[3] = (cdir+5) % 8, dirs[4] = (cdir+2) % 8, dirs[5] = (cdir+6) % 8;
		
		for (i=1; i<=5; i++)
			if ( v[ cx ][ cy ][ dirs[i] ]==1 )
				expand( setflags(cx+dx[dirs[i]], cy+dy[dirs[i]], ttf(dirs[i])), costs[i]+d[cflag] );

		rez=looplist();
		
		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;
}