Cod sursa(job #651920)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 22 decembrie 2011 13:15:06
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 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;
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];

struct elem{
	elem(int x = 0,int y = 0,int d = 0):x(x),y(y),d(d){}
	
	int x,y;
	int d;
}st;

queue<elem>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();
			
			if ( st.x == xf && st.y == yf ){
				fprintf(g,"%d\n",D[st.x][st.y][st.d]);
				return 0;
			}
			
			iv = st.x + di[st.d]; jv = st.y + dj[st.d]; dv = st.d;
			if ( iv >= 1 && iv <= n && jv >= 1 && jv <= n && (!A[iv][jv]) && D[iv][jv][dv] > D[st.x][st.y][st.d] ){
				D[iv][jv][dv] = D[st.x][st.y][st.d];
				Q[list].push(elem(iv,jv,dv));
			}
			
			iv = st.x; jv = st.y; dv = st.d + 1;
			if ( D[iv][jv][dv] > D[st.x][st.y][st.d] + 1 ){
				D[iv][jv][dv] = D[st.x][st.y][st.d] + 1;
				Q[1-list].push(elem(iv,jv,dv));
			}
			
			dv = st.d - 1; if ( dv == -1 )	dv = 7;
			if ( D[iv][jv][dv] > D[st.x][st.y][st.d] + 1 ){
				D[iv][jv][dv] = D[st.x][st.y][st.d] + 1;
				Q[1-list].push(elem(iv,jv,dv));
			}
		}
	}
	
	fprintf(g,"-1\n");
	
	fclose(f);
	fclose(g);
	
	return 0;
}