Cod sursa(job #87856)

Utilizator marius135Dumitran Adrian Marius marius135 Data 29 septembrie 2007 14:01:15
Problema Car Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include<stdio.h>

#define maxn 512

long  x[8] ={0,1,1,1,0,-1,-1,-1},y[8]={1,1,0,-1,-1,-1,0,1},n,m;
char sel[maxn][maxn][8];
long sol[4][maxn*maxn][3];
long v[maxn][maxn];

long calc(long a,long b)
{
	long c;
	if( a<b) a = a^b^(b=a);
	c =a-b;
	if(c<=4) return c;
	return 8-c;
}
long bf(long finx,long finy)
{
	long j = -1;
	long poz1,poz2,min = 1024*1204,i,dir,rq;
	while(1)
	{
		++j;
		if(j>= min) return min;
		//memset(sol[(j+3)%4],0,sizeof(sol[0]));
		sol[(j+3)%4][0][0] = 0;
		for(i = 1; i <= sol[j%4][0][0];i++)
		{
			for( dir = 0; dir <=7;dir++)
			{
				if(dir == sol[j%4][i][2] && (j!=0 || i>8 )) continue;
				long dif = calc(dir,sol[j%4][i][2]);
				if(dif==4) continue;
				if(dif!=0 && j==0 && i<=8) continue;
				poz1 = sol[j%4][i][0] + x[dir];
				poz2 = sol[j%4][i][1] + y[dir];
				while(v[poz1][poz2]==0)
				{
					if(!sel[poz1][poz2][dir])
					{
						rq = (j+dif)%4;
						sel[poz1][poz2][dir] = 1;
						sol[rq][++sol[rq][0][0]][0] = poz1;
						sol[rq][sol[rq][0][0]][1] = poz2;
						sol[rq][sol[rq][0][0]][2] = dir;
						if(j+dif<min && poz1 == finx && poz2 == finy) 
							min = j+dif;
					}
					else break;
					poz1+=x[dir];
					poz2+=y[dir];
				}
			}
		}			
		
	}
}
int main()
{
	long x1,y1,x2,y2,i,j;
	freopen("car.in","r",stdin);
	freopen("car.out","w",stdout);
	scanf("%ld %ld",&n,&m);
	scanf("%ld %ld %ld %ld",&x1,&y1,&x2,&y2);
	for(i=0;i<=7;i++)
		{
		sol[0][i+1][0] = x1;
		sol[0][i+1][1] = y1;
		sol[0][i+1][2] = i;
		sol[0][0][0] = 8;
		}
	for(i=0;i<=n+1;i++)
		for(j=0;j<=m+1;j++)
			v[i][j] = 1;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			scanf("%ld",&v[i][j]);
	printf("%ld\n",bf(x2,y2));
	
	
	return 0;
}