Cod sursa(job #384114)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 19 ianuarie 2010 10:07:15
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <stdio.h>
#include <queue>
using namespace std;
#define NMAX 512
#define INF 2000000000
//queue <int> q[5];
int q[3][NMAX*NMAX];
int A[8][8];
int F[NMAX*NMAX*8];
bool B[NMAX][NMAX], OK[NMAX*NMAX*8];
int n, m, X, Y, x2, y2;
const int lin[] = {0, -1, -1, -1, 0, 1, 1, 1};
const int col[] = {1, 1, 0, -1, -1, -1, 0, 1};
const int dir[] = {0, 1, 2, 3, 4, 5, 6, 7};
/*const int lin[] = {0, -1, -1, 1, 1};
const int col[] = {1, */
void precalc(){
	int c = 0;
	for(int i = 0; i < 8; ++i, c = 0)
		for(int j = i+1; j < 8; ++j)
			if(j - i <= 4) A[i][j] = A[j][i] = ++c;
			else A[i][j] = A[j][i] = --c;
}
void init(){
	for(int t = 0; t < 8; ++t)
		if( B[X+lin[t]][Y+col[t]] ){
			q[0][++q[0][0]] = ( dir[t] + ((X+lin[t])<<3) + ((Y+col[t])<<12) );
			//OK[dir[t] + ((X+lin[t])<<3) + ((Y+col[t])<<12)] = true;
		}
	for(int t = 0; t < 8; ++t)
		OK[t + (X<<3) + (Y<<12)] = true;
}
int mod(int x){
	int y;
	if(x > 0)
		y = x;
	else y = - x;
	return (y >= 3 && y <=5);
	//return 1;
}
void vecini(int p, int i){
	int x, y, d;
	d = (p & 7);
	x = ((p>>3) & 511); //(p & 4088);
	y = ((p>>12) & 511); //(p & 6132);
	for(int t = 0; t < 8; ++t)
		if(B[x+lin[t]][y+col[t]]){
			//int xx = x+lin[t], yy = y + col[t];
			int o = dir[t] + ((x+lin[t])<<3) + ((y+col[t])<<12);
			if(OK[o] || mod(d-t)) continue;
			if(F[o] && F[p] + A[d][dir[t]] >= F[o]) continue;
		//	OK[o] = true;
			q[(i+A[d][dir[t]]) % 3][++q[(i+A[d][dir[t]]) % 3][0]] = o;
			F[o] = F[p] + A[d][dir[t]];
		}
}
void solve(){
	int i, x, j;
	int ok = 0;
	for(i = 0; ok <= 3; i = (i+1)%3)
		if(q[i][0]){
			//while(q[i][0]){
				//x = q[i].front();
				//q[i].pop();
			for(j = 1; j <= q[i][0]; ++j){
				x = q[i][j];
				if(!OK[x]) {
					ok = 0;
					OK[x] = 1;
					vecini(x, i);
				}
			}
			q[i][0] = 0;
		}
		else ok++;
	int sol = INF;
	int w = (x2<<3) + (y2<<12);
	for(i = 0 ; i < 8; ++i)
		if(OK[w+i] && sol > F[w+i]) sol = F[w+i];
	printf("%d\n", sol != INF ? sol : -1);
}
int main(){
	freopen("car.in", "r", stdin);
	freopen("car.out", "w", stdout);
	precalc();
	scanf("%d%d", &m, &n);
	scanf("%d%d%d%d",&X, &Y, &x2, &y2);
	int x;
	for(int i = 1; i <= m; ++i)
		for(int j = 1; j <= n; ++j){
			scanf("%d", &x);
			if(x==0) B[i][j] = true;
		}
	if(!B[x2][y2] || !B[X][Y]) {
		printf("-1\n");
		return 0;
	}
	init();
	solve();
	return 0;
}