Cod sursa(job #384012)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 18 ianuarie 2010 21:30:53
Problema Car Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <stdio.h>
#include <queue>
using namespace std;
#define NMAX 512
queue <int> q[5];
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].push( 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;*/
	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]) continue;
			if(F[o] && F[p] + A[d][dir[t]] >= F[o]) continue;
		//	OK[o] = true;
			q[ (i+A[d][dir[t]]) % 5].push(o);
			F[o] = F[p] + A[d][dir[t]];
		}
}
void solve(){
	int i, x;
	int ok = 0;
	for(i = 0; ok <= 4; i = (i+1)%5)
		if(!q[i].empty() ){
			while( !q[i].empty() ){
				x = q[i].front();
				q[i].pop();
				if(!OK[x]) {
					ok = 0;
					OK[x] = 1;
					vecini(x, i);
				}
			}
		}
		else ok++;
	int sol = 2000000000;
	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);
}
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]) {
		printf("-1\n");
		return 0;
	}
	init();
	solve();
	return 0;
}