Cod sursa(job #441635)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 13 aprilie 2010 00:04:03
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.28 kb
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int NMAX=502;
char L[NMAX*NMAX*8+4][8];
int dl[]={-1,-1, 0, 1, 1, 1, 0,-1};
int dc[]={ 0, 1, 1, 1, 0,-1,-1,-1};
char co[9][8]={{0,1,2,3,4,3,2,1},
			   {1,0,1,2,3,4,3,2},
			   {2,1,0,1,2,3,4,3},
			   {3,2,1,0,1,2,3,4},
			   {4,3,2,1,0,1,2,3},
			   {3,4,3,2,1,0,1,2},
			   {2,3,4,3,2,1,0,1},
			   {1,2,3,4,3,2,1,0},
			   {0,0,0,0,0,0,0,0}};
int minim,n,m,pix,piy,pfx,pfy,cost[NMAX*NMAX*8+4];
bool f[NMAX*NMAX*8+4],a[NMAX][NMAX];
short int px[NMAX*NMAX*8+4],py[NMAX*NMAX*8+4];
queue<int> Q;
void citire()
{
	char s[1025];
	scanf("%d%d%d%d%d%d\n",&n,&m,&pix,&piy,&pfx,&pfy);
	for(short int i=1;i<=n;++i)
	{
		gets(s+1);
		for(short int j=1;s[j];j+=2)
			if(s[j]=='1')
				a[i][(j+1)>>1]=true;
	}
}
void bordare()
{
    for(short int i=0;i<=n+1;++i)
        a[i][0]=a[i][m+1]=true;
    for(short int j=0;j<=m+1;++j)
        a[0][j]=a[n+1][j]=true;
}
void graf()
{
	for(short int i=1;i<=n;++i)
		for(short int j=1;j<=m;++j)
			for(short int k=0;k<8;++k)
			{
				for(short int l=0;l<8;++l)
					if(a[i+dl[l]][j+dc[l]]==false)
						L[(i-1)*m*8+(j-1)*8+k][l]=co[k][l];
					else L[(i-1)*m*8+(j-1)*8+k][l]=-1;
				px[(i-1)*m*8+(j-1)*8+k]=i;
				py[(i-1)*m*8+(j-1)*8+k]=j;
			}
	int i=pix;
	int j=piy;
	for(short int l=0;l<8;++l)
		if(a[i+dl[l]][j+dc[l]]==false)
			L[n*8*m+1][l]=co[8][l];
		else L[n*8*m+1][l]=-1;
	px[n*8*m+1]=pix;
	py[n*8*m+1]=piy;
}

void bf()
{
	Q.push(n*8*m+1);
	f[n*m*8+1]=true;
	int cc,nod,x;
	cost[n*m*8+1]=1;
	while(!Q.empty())
	{
		x=Q.front();
		for(short int i=0;i<8;++i)
			if(L[x][i]>=0)
			{
				nod=(px[x]+dl[i]-1)*m*8+(py[x]+dc[i]-1)*8+i;
				cc=L[x][i];
				if(cost[x]+cc<cost[nod] || cost[nod]==0)
				{
					cost[nod]=cost[x]+cc;
					if(!f[nod])
					{
						f[nod]=true;
						Q.push(nod);
					}
				}
			}
		f[x]=false;
		Q.pop();
	}
}
int main()
{
	freopen("car.in","r",stdin);
	freopen("car.out","w",stdout);
	citire();
	bordare();
	graf();
	bf();
	minim=2000000000;
	for(short int i=0;i<8;++i)
		if(minim>cost[(pfx-1)*m*8+(pfy-1)*8+i] && cost[(pfx-1)*m*8+(pfy-1)*8+i])
			minim=cost[(pfx-1)*m*8+(pfy-1)*8+i];
	if(minim==2000000000)
	{
		printf("-1");
		return 0;
	}
	printf("%d",minim-1);
	return 0;
}