Cod sursa(job #430015)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 30 martie 2010 17:55:21
Problema Car Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include<cstdio>
#include<queue>
using namespace std;
int pix,piy,pfx,pfy,n,m,a[1<<9][1<<9],cost[1<<9][1<<9];
bool f[1<<9][1<<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}};
queue<pair<int,int> > Q;
queue<int> D;
void afis()
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			printf("%d ",cost[i][j]);
		printf("\n");
	}
	printf("\n\n");
}
void bf()
{
	Q.push(make_pair(pix,piy));
	D.push(8);
	int xc,yc,d,xf,yf;
	xc=yc=d=xf=yf=0;
	cost[pix][piy]=1;
	f[pix][piy]=true;
	while(!Q.empty())
	{
		xc=Q.front().first;
		yc=Q.front().second;
		d=D.front();
		for(int i=0;i<8;i++)
		{
			xf=xc+dl[i];
			yf=yc+dc[i];
			if(a[xf][yf]==0)
			{
				if(cost[xf][yf]>cost[xc][yc]+co[d][i])
				{
					cost[xf][yf]=cost[xc][yc]+co[d][i];
					if(!f[xf][yf])
					{
						f[xf][yf]=true;
						Q.push(make_pair(xf,yf));
						D.push(i);
					}
					continue;
				}
				if(cost[xf][yf]==0)
				{
					cost[xf][yf]=cost[xc][yc]+co[d][i];
					f[xf][yf]=true;
					Q.push(make_pair(xf,yf));
					D.push(i);
				}
			}
		}
		f[xc][yc]=false;
		Q.pop();
		D.pop();
		//afis();
	}
}
void citire()
{
	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",&a[i][j]);
}
void bordare()
{
	for(int i=0;i<=n+1;i++)
		a[i][0]=a[i][m+1]=1;
	for(int j=0;j<=m+1;j++)
		a[0][j]=a[n+1][j]=1;
}
int main()
{
	freopen("car.in","r",stdin);
	freopen("car.out","w",stdout);
	citire();
	bordare();
	bf();
	printf("%d",cost[pfx][pfy]-1);
	return 0;
}