Cod sursa(job #651921)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 22 decembrie 2011 13:21:37
Problema Car Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include<stdio.h>
#include<queue>

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

using namespace std;

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

int n,m,xi,yi,xf,yf,i,j,iv,jv,dv,d,list,st,stx,sty,stdir;
int A[maxn][maxn];

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

inline int elem ( int x , int y , int d ){
	int r = (d << 18) + (x<<9) + y;
	return r;
}

queue<int>Q[2];

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 ){
		D[xi][yi][d] = 0;
		Q[0].push(elem(xi,yi,d));
	}
	
	for ( list = 1 ; Q[0].size() + Q[1].size() > 0 ; ){
		list = 1 - list;
		
		while ( !Q[list].empty() ){
			st = Q[list].front(); Q[list].pop();
			stdir = st >> 18; sty = st & 511; stx = (st>>9)&511;
			
			if ( stx == xf && sty == yf ){
				fprintf(g,"%d\n",D[stx][sty][stdir]);
				return 0;
			}
			
			iv = stx + di[stdir]; jv = sty + dj[stdir]; dv = stdir;
			if ( iv >= 1 && iv <= n && jv >= 1 && jv <= n && (!A[iv][jv]) && D[iv][jv][dv] > D[stx][sty][stdir] ){
				D[iv][jv][dv] = D[stx][sty][stdir];
				Q[list].push(elem(iv,jv,dv));
			}
			
			iv = stx; jv = sty; dv = stdir + 1;
			if ( D[iv][jv][dv] > D[stx][sty][stdir] + 1 ){
				D[iv][jv][dv] = D[stx][sty][stdir] + 1;
				Q[1-list].push(elem(iv,jv,dv));
			}
			
			dv = stdir - 1; if ( dv == -1 )	dv = 7;
			if ( D[iv][jv][dv] > D[stx][sty][stdir] + 1 ){
				D[iv][jv][dv] = D[stx][sty][stdir] + 1;
				Q[1-list].push(elem(iv,jv,dv));
			}
		}
	}
	
	fprintf(g,"-1\n");
	
	fclose(f);
	fclose(g);
	
	return 0;
}