Cod sursa(job #441568)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 12 aprilie 2010 23:18:44
Problema Car Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int NMAX=502;
vector<pair<int,char> > L[NMAX*NMAX*9];
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*9];
bool f[NMAX*NMAX*9],a[NMAX][NMAX];
queue<int> Q;
void citire()
{
	int x;
	scanf("%d%d%d%d%d%d",&n,&m,&pix,&piy,&pfx,&pfy);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{ 
			scanf("%d",&x);
			if(x==1)
				a[i][j]=true;
		}
}
void bordare()
{
    for(int i=0;i<=n+1;i++)
        a[i][0]=a[i][m+1]=true;
    for(int j=0;j<=m+1;j++)
        a[0][j]=a[n+1][j]=true;
}
void graf()
{
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			for(int k=0;k<8;k++)
			{
				for(int l=0;l<8;l++)
					if(a[i+dl[l]][j+dc[l]]==false)
						L[(i-1)*m*8+(j-1)*8+k].push_back(make_pair((i+dl[l]-1)*m*8+(j+dc[l]-1)*8+l,co[k][l]));
			}
	int i=pix;
	int j=piy;
	for(int l=0;l<8;l++)
		if(a[i+dl[l]][j+dc[l]]==false)
			L[n*8*m+1].push_back(make_pair((i+dl[l]-1)*m*8+(j+dc[l]-1)*8+l,co[8][l]));
}
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(vector<pair<int,char> >::iterator it=L[x].begin();it!=L[x].end();it++)
		{
			nod=it->first;
			cc=it->second;
			if(cost[x]+cc<cost[nod] || cost[nod]==0)
			{
				cost[nod]=cost[x]+cc;
				if(!f[nod])
					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(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;
}