Cod sursa(job #486832)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 22 septembrie 2010 21:09:30
Problema Car Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <cstdio>

#define file_in "car.in"
#define file_out "car.out"

const int nmax=555;

int n,m;
int xi,yi,xf,yf;
int a[nmax][nmax];
int d[nmax][nmax];
int cost[nmax][nmax];
int qx[nmax*nmax];
int qy[nmax*nmax];


void adfile(void){
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d", &n, &m);
	scanf("%d %d %d %d", &xi, &yi, &xf, &yf);
	int i,j;
	for (i=1;i<=n;++i)
		for (j=1;j<=m;++j){
			scanf("%d", &a[i][j]);
			cost[i][j]=0x3f3f3f3f;
		}
		
	fclose(stdin);

	return ;
	
}

const int dx[9]={0,-1,-1,-1,0,1,1,1,0};  
const int dy[9]={0,-1,0,1,1,1,0,-1,-1};

int misca[9][9]={
	{0,0,0,0,0,0,0,0,0},
	{0,0,1,2,3,4,3,2,1},
	{0,1,0,1,2,3,4,3,2},
	{0,2,1,0,1,2,3,4,3},
	{0,3,2,1,0,1,2,3,4},
	{0,4,3,2,1,0,1,2,3},
	{0,3,4,3,2,1,0,1,2},
	{0,2,3,4,3,2,1,0,1},
	{0,1,2,3,4,3,2,1,0}};
	

void solve(void){
	
	int p,u,xx,yy,lne,cne,k;
	
	p=u=1;
	qx[1]=xi;
	qy[1]=yi;
	cost[xi][yi]=0;
	
	while(p<=u){
		
		xx=qx[p];
		yy=qy[p];
		p++;
		
		for (k=1;k<=8;++k){
			lne=xx+dx[k];
			cne=yy+dy[k];
			
			if (a[lne][cne]==0 && lne<=n && lne>=1 && cne<=m && cne>=1){
				
				if (cost[lne][cne]>cost[xx][yy]+misca[d[xx][yy]][k]){
				    cost[lne][cne]=cost[xx][yy]+misca[d[xx][yy]][k];
					qx[++u]=lne;
					qy[u]=cne;
					d[lne][cne]=k;
				}
			}
		}
	}
	
	if (cost[xf][yf]==0x3f3f3f3f)
		printf("-1\n");
	else
		printf("%d\n", cost[xf][yf]);
}

int main(){
	
	adfile();
	solve();
	
	return 0;
	
}