Cod sursa(job #484758)

Utilizator indestructiblecont de teste indestructible Data 15 septembrie 2010 18:43:07
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.53 kb
#include <stdio.h>
#include <vector>
#include <queue>
#define NMAX 505
#define DIR 8
#define pb push_back
#define INF 2000000000
#define VMAX 2500005
using namespace std;
int n,m,c1,c2,c3,c4;
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 <int> Q;
bool in[VMAX];
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 i,int j,int dir)
{
	return (i<<9)+j+(dir<<18);
}
void init()
{
	int i,j,k,x;
	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++)
	{
		x=codif(c1,c2,k); in[x]=1;
		best[c1][c2][k]=0,Q.push(x);
	}
}
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,x2;
	init();
	while (!Q.empty())
	{
		x=Q.front();
		dir=x>>18; b=(x&511); a=(x>>9)&511;
		Q.pop(); in[x]=0; 
		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];
			x2=codif(a1,b1,tip);
			if (!in[x2])
				Q.push(x2),in[x2]=1;
		}
		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;
			x2=codif(a1,b1,tip);
			if (!in[x2])
				Q.push(x2),in[x2]=1;
		}
		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;
			x2=codif(a1,b1,tip);
			if (!in[x2])
				Q.push(x2),in[x2]=1;
		}
		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;
			x2=codif(a1,b1,tip);
			if (!in[x2])
				Q.push(x2),in[x2]=1;
		}
		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;
			x2=codif(a1,b1,tip);
			if (!in[x2])
				Q.push(x2),in[x2]=1;
		}
	}
	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;
}