Cod sursa(job #52603)

Utilizator alextheroTandrau Alexandru alexthero Data 19 aprilie 2007 13:33:34
Problema Car Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <stdio.h>

#define viz 1
#define inf (int)1e9
#define valmax 1 << 21
#define nmax 512

int vx[] = {1,1,0,-1,-1,-1,0,1};
int vy[] = {0,-1,-1,-1,0,1,1,1};
int v1,v2,i,j,dx,n,m,sx,sy,fx,fy,a[nmax][nmax],cost,rez = inf,nd,n1,n2,n3,gata = 0,nd1;
int Q[3][valmax],ax;
char v[valmax][3];

inline int bun(int x,int y) {
	if(x < 1 || x > n || y < 1 || y > m) return 0;
	if(a[x][y] == 1) return 0;
	return 1;
}

inline int code(int x,int y,int d) {
	return (x << 9) + y + (d << 18);
}

void exp(int nod) {
	n1 = (nod >> 9) & 511,n2 = (nod & 511),n3 = nod >> 18;
	if(n1 == fx && n2 == fy) {
		rez = cost;
		gata = 1;
		return ;
	}
	nd = n3 + 1,nd1 = n3 - 1;
	for(i = 0; i <= 2; i++) {
		nd--;
		if(nd < 0) nd = 7;
		v1 = (cost + i) % 3;
		v2 = code(n1 + vx[nd],n2 + vy[nd],nd);
		if(bun(n1 + vx[nd],n2 + vy[nd]) && !v[v2][v1]) {
			Q[v1][++Q[v1][0]] = v2;
			if(viz) v[v2][v1] = 1;
		}
		nd1++;
		if(nd1 > 7) nd1 = 0;
		v2 = code(n1 + vx[nd1],n2 + vy[nd1],nd1);
		if(bun(n1 + vx[nd1],n2 + vy[nd1]) && !v[v2][v1]) {
			Q[v1][++Q[v1][0]] = v2;
			if(viz) v[v2][v1] = 1;
		}
	}
}

int main() {
	freopen("car.in","r",stdin);
	freopen("car.out","w",stdout);

	scanf("%d%d",&n,&m);
	scanf("%d%d%d%d",&sx,&sy,&fx,&fy);

	for(i = 1; i <= n; i++) 
		for(j = 1; j <= m; j++) scanf("%d",&a[i][j]);

	for(dx = 0; dx < 8; dx++) {
		Q[0][++Q[0][0]] = code(sx,sy,dx);
		v[Q[0][Q[0][0]]][0] = 1;
	}

	cost = 0,rez = -1;
	while(Q[0][0] > 0 || Q[1][0] > 0 || Q[2][0] > 0) {
		while(Q[cost % 3][0] > 0) {
			ax = Q[cost % 3][Q[cost % 3][0]];
			Q[cost % 3][0]--;
			exp(ax);
			if(gata) {
				printf("%d\n",rez);
				return 0;
			}
		}
		cost++;
	}

	printf("%d\n",rez);

	return 0;
}