Cod sursa(job #20636)

Utilizator m_dersidanDersidan Mihai m_dersidan Data 21 februarie 2007 20:51:50
Problema Car Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.46 kb
# include <stdio.h>
# include <string.h>

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

# define  maxn  502
# define  maxd  9

# define  inf	25000002


typedef struct nod
{
	int x, dir, used;	// nodul + directia DIN care se vine
	nod *next;
}	*pnod;


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


int d[maxn * maxn][maxd];	// distantele
int v[maxn * maxn][maxd], viz[maxn * maxn][maxd];		// daca nodul se afla in vreo lista
int n, m, cs, ce, sol;
int cl, ml;					// lista curenta, lista maxima
pnod l[maxn*maxn], crt;		// lista pentru toate distantele

int is, js, ie, je;


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


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

void del(int x, int dir, int list)
{
/*	if ( l[list]->x==x && l[list]->dir==dir )
	{
		pnod tmp = l[list];
		l[list]=l[list]->next;
		delete tmp;
	}
	else
	{
		pnod tmp, i;
		for (i=l[list]; i->next && !( i->x==x && i->dir==dir ); i=i->next);
		tmp = i->next, i->next = tmp->next;

		delete tmp;
	} */

//	viz[ x ][ dir ] = 1;

//	TEST
//	mark the node as unused
	pnod i;
	
	for (i=l[ list ]; i->x != x || i->dir != dir; i = i->next);
	
	i -> used = 0;
	
	viz[ x ][ dir ] = 0;	// unvisited
}

inline void getfirst(int &x, int &dir) { x = crt->x, dir = crt->dir; }

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

	if ( !crt )
		while ( !crt && cl <= ml )
		{
//			dellist(cl);
			crt = l[ ++cl ];
		}
}

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);
	
	cs = encode(is, js), ce = encode(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[ encode(i, j) ][ k ] = 1;	// se poate merge in directia k
}

void expand(int x, int newd, int dir)
// nodul, distanta noua, directia DIN care se vine
// apelata numai daca newd < d || d == inf
{
	if ( newd >= d[ x ][ dir ] ) return;

	if ( viz[ x ][ dir ] )							// already in some list, higher than the current one
		del( x, dir, d[x][dir] );
	
	insert(x, dir, newd);
	d[ x ][ dir ] = newd;
	
	if ( newd > ml ) ml = newd;
}

int getcode(int cn, int dir)
{
	int ci, cj;
	
	decode(cn, ci, cj);
	ci += dx[dir], cj += dy[dir];
	
	return encode(ci, cj);
}

void solve()
{
	int i, j, k, dirs[maxd], costs[maxd];			// directiile spre care plecam, costurile pt. fiecare in parte
	int cn, cdir;
	
	for (i=0; i<maxn*maxn; i++)
		for (j=0; j<8; j++)	d[i][j] = inf;
	
	for (i=0; i<8; i++)
		if ( v[cs][i]==1 )
			expand( getcode(cs, i), 0, ttf(i) );	// noul nod, directia din care se ajunge in el, costul momentan
	
	cl = ml = 0;
	crt = l[0];
	
	while ( cl <= ml )
	{
		// if ( extract(cn, cdir)==-1 ) continue;
		// cn = crt->x, cdir = crt->dir;
		getfirst(cn, cdir);
		
		// creez distantele in care se poate pleca
		memset(dirs, 0, sizeof(dirs));
		memset(costs, 0, sizeof(costs));
		
		dirs[ ++dirs[0] ] = (cdir+4) % 8, costs[ dirs[0] ] = 0;
		dirs[ ++dirs[0] ] = (cdir+3) % 8, costs[ dirs[0] ] = 1;
		dirs[ ++dirs[0] ] = (cdir+5) % 8, costs[ dirs[0] ] = 1;
		dirs[ ++dirs[0] ] = (cdir+2) % 8, costs[ dirs[0] ] = 2;
		dirs[ ++dirs[0] ] = (cdir+6) % 8, costs[ dirs[0] ] = 2;
		
		for (i=1; i<=dirs[0]; i++)
			if ( v[ cn ][ dirs[i] ]==1 )
				expand( getcode( cn, dirs[i] ), costs[i] + d[ cn ][ cdir ], ttf(dirs[i]) );

		looplist();
		while ( cl <= ml && !(crt->used) )		// jump over unused nodes
			looplist();
	}

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

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

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