Cod sursa(job #441016)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 12 aprilie 2010 18:43:14
Problema Car Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.13 kb
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int NMAX=501;
vector<pair<int,int> > L[NMAX*NMAX*9];
int dl[]={-1,-1, 0, 1, 1, 1, 0,-1};
int dc[]={ 0, 1, 1, 1, 0,-1,-1,-1};
int 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],ord[NMAX][NMAX][9];
bool f[NMAX*NMAX*9],a[NMAX][NMAX];
queue<int> Q;
void citire()
{
	int q=0,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;
			for(int k=0;k<8;k++)
				ord[i][j][k]=++q;
			if(i==pix && j==piy)
				ord[i][j][8]=++q;
			
		}
}
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[ord[i][j][k]].push_back(make_pair(ord[i+dl[l]][j+dc[l]][l],co[k][l]));
			}
			if(i==pix && j==piy)
			{
				for(int l=0;l<8;l++)
					if(a[i+dl[l]][j+dc[l]]==false)
						L[ord[i][j][8]].push_back(make_pair(ord[i+dl[l]][j+dc[l]][l],co[8][l]));
			}
		}
}
void bf()
{
	Q.push(ord[pix][piy][8]);
	f[ord[pix][piy][8]]=true;
	int cc,nod,x;
	cost[ord[pix][piy][8]]=1;
	while(!Q.empty())
	{
		x=Q.front();
		for(vector<pair<int,int> >::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[ord[pfx][pfy][i]] && cost[ord[pfx][pfy][i]])
			minim=cost[ord[pfx][pfy][i]];
	if(minim==2000000000)
	{
		printf("-1");
		return 0;
	}
	printf("%d",minim-1);
	return 0;
}