Cod sursa(job #651919)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 22 decembrie 2011 12:28:15
Problema Car Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.79 kb
#include<stdio.h>

#define maxn 505
#define INF (1<<29)

FILE*f=fopen("car.in","r");
FILE*g=fopen("car.out","w");

int n,m,xi,yi,xf,yf,i,j,ic,jc,dc,iv,jv,dv,d,L;
int A[maxn][maxn];

const int cst[8][8] = {0,1,2,3,4,3,2,1,1,0,1,2,3,4,3,2,2,1,0,1,2,3,4,3,3,2,1,0,1,2,3,4,4,3,2,1,0,1,2,3,3,4,3,2,1,0,1,2,2,3,4,3,2,1,0,1,1,2,3,4,3,2,1,0};
int di[] = {0,1,1,1,0,-1,-1,-1};
int dj[] = {1,1,0,-1,-1,-1,0,1};
int D[maxn][maxn][8],Poz[maxn][maxn][8];

struct _heap{
	_heap(int x = 0,int y = 0,int d = 0):x(x),y(y),d(d){}
	
	int x,y;
	int d;
}H[maxn*maxn*8];

inline void swap_heap ( _heap &a , _heap &b ){
	_heap aux = a; a = b; b = aux;
}

inline void swap ( int &a , int &b ){
	int aux = a; a = b; b = aux;
}

inline void urca(int poz){
	
	while ( poz && D[H[poz>>1].x][H[poz>>1].y][H[poz>>1].d] > D[H[poz].x][H[poz].y][H[poz].d] ){
		swap_heap(H[poz],H[poz>>1]);
		swap(Poz[H[poz>>1].x][H[poz>>1].y][H[poz>>1].d],Poz[H[poz].x][H[poz].y][H[poz].d]);
		poz = poz >> 1;
	}
}

inline void coboara(int x){
	int y = 0;
	
	while ( x != y ){
		y = x;
		if ( (y << 1) <= L && D[H[y<<1].x][H[y<<1].y][H[y<<1].d] < D[H[x].x][H[x].y][H[x].d] )
			x = y << 1;
		if ( (y << 1) + 1 <= L && D[H[(y<<1)+1].x][H[(y<<1)+1].y][H[(y<<1)+1].d] < D[H[x].x][H[x].y][H[x].d] )
			x = ( y << 1 ) + 1;
		swap_heap(H[x],H[y]);
		swap(Poz[H[x].x][H[x].y][H[x].d],Poz[H[y].x][H[y].y][H[y].d]);
	}
}

inline void add_heap ( int i , int j , int d ){
	
	H[++L] = _heap(i,j,d);
	Poz[i][j][d] = L;
	urca(L);
}

inline void erase_first (){
	
	swap_heap(H[1],H[L]);
	swap(Poz[H[1].x][H[1].y][H[1].d],Poz[H[L].x][H[L].y][H[L].d]);
	--L;
	coboara(1);
}

int main () {
	
	fscanf(f,"%d %d",&n,&m);
	fscanf(f,"%d %d %d %d",&xi,&yi,&xf,&yf);
	
	for ( i = 1 ; i <= n ; ++i ){
		for ( j = 1 ; j <= m ; ++j ){
			fscanf(f,"%d",&A[i][j]);
			for ( d = 0 ; d < 8 ; ++d ){
				D[i][j][d] = INF;
			}
		}
	}
	
	for ( d = 0 ; d < 8 ; ++d ){
		iv = xi + di[d]; jv = yi + dj[d];
		if ( iv >= 1 && iv <= n && jv >= 1 && jv <= m && !A[iv][jv] ){
			D[iv][jv][d] = 0;
			add_heap(iv,jv,d);
		}
	}
	
	while ( L ){
		ic = H[1].x; jc = H[1].y; dc = H[1].d; erase_first();
		
		for ( d = 0 ; d < 8 ; ++d ){
			iv = ic + di[d]; jv = jc + dj[d]; dv = d;
			if ( iv >= 1 && iv <= n && jv >= 1 && jv <= m && !A[iv][jv] ){
				if ( D[iv][jv][dv] > D[ic][jc][dc] + cst[dc][dv] ){
					D[iv][jv][dv] = D[ic][jc][dc] + cst[dc][dv];
					
					if ( Poz[iv][jv][dv] ){
						urca(Poz[iv][jv][dv]);
					}
					else{
						add_heap(iv,jv,d);
					}
				}
			}
		}
	}
	
	int best = INF;
	
	for ( d = 0 ; d < 8 ; ++d ){
		if ( D[xf][yf][d] < best ){
			best = D[xf][yf][d];
		}
	}
	
	if ( best != INF ){
		fprintf(g,"%d\n",best);
	}
	else{
		fprintf(g,"-1\n");
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}