Cod sursa(job #442433)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 14 aprilie 2010 15:59:39
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
int n,m,cost,x1,y1,x2,y2,v[502][502];
int d[(1<<21)^2];
int dx[]={-1,-1,0,1,1,1,0,-1};
int dy[]={0,1,1,1,0,-1,-1,-1};
queue<int> q[2];

inline int code(int x, int y, int dir){return (dir<<18)+(x<<9)+y;}
inline void decode(int &x, int &y, int &dir, int nod)
{
	y=nod&511;
	x=(nod>>9)&511;
	dir=nod>>18;
}

inline void add(int nod1, int nod2, int c)
{
	if(d[nod1]+c<d[nod2])
	{
		d[nod2]=d[nod1]+c;
		q[d[nod2]&1].push(nod2);
	}
}

void expand(int nod)
{
	int x,y,dir;
	decode(x,y,dir,nod);
	add(nod,code(x,y,(dir+1)&7),1);
	add(nod,code(x,y,(dir+7)&7),1);
	x+=dx[dir];
	y+=dy[dir];
	if(!v[x][y])
	{
		if(x==x2 && y==y2)
		{
			printf("%d\n",cost);
			while(!q[0].empty())
				q[0].pop();
			while(!q[1].empty())
				q[1].pop();
			return;
		}
		add(nod,code(x,y,dir),0);
	}
}

int main()
{
	freopen("car.in","r",stdin);
	freopen("car.out","w",stdout);
	scanf("%d%d",&n,&m);
	scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
	int i,j,nod;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			scanf("%d",&v[i][j]);
	for(i=0;i<=n+1;i++)
		v[i][0]=v[i][m+1]=1;
	for(j=0;j<=m+1;j++)
		v[0][j]=v[n+1][j]=1;
	memset(d,0x3f3f3f3f,sizeof(d));
	for(i=0;i<8;i++)
	{
		nod=code(x1,y1,i);
		d[nod]=0;
		q[0].push(nod);
	}
	int ind;
	while(q[0].size()+q[1].size())
	{
		ind=cost&1;
		while(!q[ind].empty())
		{
			nod=q[ind].front();
			q[ind].pop();
			expand(nod);
		}
		cost++;
	}
	return 0;
}