Cod sursa(job #52595)

Utilizator alextheroTandrau Alexandru alexthero Data 19 aprilie 2007 13:04:39
Problema Car Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <stdio.h>
#include <queue>

#define viz 1
#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,nd1;
char v[nmax][nmax][8][3];
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;
	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;
		if(bun(n1 + vx[nd],n2 + vy[nd]) && !v[n1 + vx[nd]][n2 + vy[nd]][nd][(cost + i) %3]) {
			Q[(cost + i) % 3].push(per(ii(n1 + vx[nd],n2 + vy[nd]),nd));
			if(viz) v[n1 + vx[nd]][n2 + vy[nd]][nd][(cost + i) % 3] = 1;
		}
		nd1++;
		if(nd1 > 7) nd1 = 0;
		if(bun(n1 + vx[nd1],n2 + vy[nd1]) && !v[n1 + vx[nd1]][n2 + vy[nd1]][nd1][(cost + i) % 3]) {
			Q[(cost + i) % 3].push(per(ii(n1 + vx[nd1],n2 + vy[nd1]),nd1));
			if(viz) v[n1 + vx[nd1]][n2 + vy[nd1]][nd1][(cost + i) % 3] = 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].push(per(ii(sx,sy),dx));
		v[sx][sy][dx][0] = 1;
	}

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