Cod sursa(job #52589)

Utilizator alextheroTandrau Alexandru alexthero Data 19 aprilie 2007 12:41:32
Problema Car Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <stdio.h>
#include <queue>

#define inf (int)1e9
#define nmax 512

using namespace std;
typedef pair<int,int> ii;
typedef pair<pair<int,int>,int> per;

int vx[] = {1,1,0,-1,-1,-1,0,1};
int vy[] = {0,-1,-1,-1,0,1,1,1};
int i,j,dx,n,m,sx,sy,fx,fy,a[nmax][nmax],cost,rez = inf,nd,n1,n2,n3,gata = 0;
queue <per> Q[3];
per ax;

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;
}

void exp(per nod) {
	n1 = nod.first.first,n2 = nod.first.second,n3 = nod.second;
	// printf("expand(%d %d %d)\n",n1,n2,n3);
	if(n1 == fx && n2 == fy) {
		rez = cost;
		gata = 1;
		return ;
	}
	nd = n3 + 1;
	for(i = 0; i <= 2; i++) {
		nd--;
		if(nd < 0) nd = 7;
		if(bun(n1 + vx[nd],n2 + vy[nd])) {
		//	printf("baga %d - %d %d %d\n",(cost + i) % 3,n1 + vx[nd],n2 + vy[nd],nd);
			Q[(cost + i) % 3].push(per(ii(n1 + vx[nd],n2 + vy[nd]),nd));
		}
	}
	nd = n3 - 1;
	for(i = 0; i <= 2; i++) {
		nd++;
		if(nd > 7) nd = 0;
		if(bun(n1 + vx[nd],n2 + vy[nd])) {
		//	printf("baga %d - %d %d %d\n",(cost + i) % 3,n1 + vx[nd],n2 + vy[nd],nd);
			Q[(cost + i) % 3].push(per(ii(n1 + vx[nd],n2 + vy[nd]),nd));
		}
	}
}

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].push(per(ii(sx,sy),dx));

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

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

	return 0;
}