Cod sursa(job #484626)

Utilizator indestructiblecont de teste indestructible Data 14 septembrie 2010 22:44:10
Problema Car Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.88 kb
#include <stdio.h>
#include <vector>
#include <queue>
#define NMAX 505
#define DIR 8
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define INF 2000000000
using namespace std;
int n,m,c1,c2,c3,c4,nrop;
int A[NMAX][NMAX];
int dlin[]={-1,-1,-1,0,1,1,1,0};
int dcol[]={-1,0,1,1,1,0,-1,-1};
int best[NMAX][NMAX][DIR],rez;
queue < pair<int,int> > Q;
void read()
{
	scanf("%d%d%d%d%d%d",&n,&m,&c1,&c2,&c3,&c4);
	int i,j;
	for (i=1; i<=n; i++)
		for (j=1; j<=m; j++)
		{
			scanf("%d",&A[i][j]);
			A[i][j]=!A[i][j];
		}
}
inline int codif(int x,int y)
{
	return x*1000+y;
}
void init()
{
	int i,j,k;
	for (i=1; i<=n; i++)
		for (j=1; j<=m; j++)
			for (k=0; k<8; k++)
				best[i][j][k]=INF;
	for (k=0; k<8; k++)
		best[c1][c2][k]=0,Q.push(mp(codif(c1,c2),k));
}
inline int modulo(int x)
{
	x=x<0 ? x+8 : x;
	x=x>=8 ? x-8 : x;
	return x;
}
inline int min(int x,int y)
{
	return x<y ? x : y;
}
void solve()
{
	int i,x,a,b,a1,b1,dir,tip;
	init();
	while (!Q.empty())
	{
		x=Q.front().f,dir=Q.front().s;
		a=x/1000; b=x-x/1000*1000;
		nrop++;
		if (nrop>2000000)
			break ;
		Q.pop();
		tip=dir;//directia de mers
		a1=a+dlin[tip]; b1=b+dcol[tip];
		if (best[a1][b1][tip]>best[a][b][dir] && A[a1][b1])
			best[a1][b1][tip]=best[a][b][dir],Q.push(mp(codif(a1,b1),tip));
		tip=modulo(dir+1);//45 grade
		a1=a+dlin[tip]; b1=b+dcol[tip];
		if (best[a1][b1][tip]>best[a][b][dir]+1 && A[a1][b1])
			best[a1][b1][tip]=best[a][b][dir]+1,Q.push(mp(codif(a1,b1),tip));
		tip=modulo(dir-1);
		a1=a+dlin[tip]; b1=b+dcol[tip];
		if (best[a1][b1][tip]>best[a][b][dir]+1 && A[a1][b1])
			best[a1][b1][tip]=best[a][b][dir]+1,Q.push(mp(codif(a1,b1),tip));
		tip=modulo(dir+2);//90 grade
		a1=a+dlin[tip]; b1=b+dcol[tip];
		if (best[a1][b1][tip]>best[a][b][dir]+2 && A[a1][b1])
			best[a1][b1][tip]=best[a][b][dir]+2,Q.push(mp(codif(a1,b1),tip));
		tip=modulo(dir-2);
		a1=a+dlin[tip]; b1=b+dcol[tip];
		if (best[a1][b1][tip]>best[a][b][dir]+2 && A[a1][b1])
			best[a1][b1][tip]=best[a][b][dir]+2,Q.push(mp(codif(a1,b1),tip));
		tip=modulo(dir+3);//135 grade
		a1=a+dlin[tip]; b1=b+dcol[tip];
		if (best[a1][b1][tip]>best[a][b][dir]+3 && A[a1][b1])
			best[a1][b1][tip]=best[a][b][dir]+3,Q.push(mp(codif(a1,b1),tip));
		tip=modulo(dir-3);
		a1=a+dlin[tip]; b1=b+dcol[tip];
		if (best[a1][b1][tip]>best[a][b][dir]+3 && A[a1][b1])
			best[a1][b1][tip]=best[a][b][dir]+3,Q.push(mp(codif(a1,b1),tip));
		tip=modulo(dir+4);//180 grade
		a1=a+dlin[tip]; b1=b+dcol[tip];
		if (best[a1][b1][tip]>best[a][b][dir]+4 && A[a1][b1])
			best[a1][b1][tip]=best[a][b][dir]+4,Q.push(mp(codif(a1,b1),tip));
	}
	rez=INF;
	for (i=0; i<8; i++)
		rez=min(rez,best[c3][c4][i]);
}
int main()
{
	freopen("car.in","r",stdin);
	freopen("car.out","w",stdout);
	read();
	solve();
	if (rez==INF)
	{
		printf("-1\n");
		return 0;
	}
	printf("%d\n",rez);
	return 0;
}