Cod sursa(job #449893)

Utilizator ConsstantinTabacu Raul Consstantin Data 7 mai 2010 08:41:39
Problema Car Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include<stdio.h>
#include<queue>
#include<string.h>
#define min(a,b) a<b?a:b

using namespace std;

queue<int>qx,qy;

bool fre[503][503],viz[503][503],ok;
int di[] = {-1,-1,0,1,1,1,0,-1},dj[] = {0,1,1,1,0,-1,-1,-1},
	dir[] = { 0,1,2,3,4,5,6,7};
int v[503][505][8],X,Y,i,j,k,l,m,n,Ix,Iy,Fx,Fy,p,a,b;


bool isIn(int x,int y){
if(x <= 0 || x > n) return false;
if(y <= 0 || y > m) return false;
if(fre[x][y])      return false;
				   return true;
}


bool check(int v[],int C,int D){
a=D,b=D-1;
ok = false;
for(register int  i=0; i < 4; i++,a++,b--)
	{if(a > 7 ) a = 0;
	 if(b < 0 ) b = 7;
	 if(v[a] > C + i)
		 {v[a] = C +i;
		 ok = true;
		 }
	if(v[b] > C + i+1)
		{v[b] = C + i+1;
		ok = true;
		}
	}
return ok;
}


int main(){
freopen("car.in","r",stdin);
freopen("car.out","w",stdout);

scanf("%d %d",&n,&m);

memset(v,100,sizeof(v));

scanf("%d %d %d %d",&Ix,&Iy,&Fx,&Fy);
for(i = 1 ; i <= n ; i++)
	for(j= 1;j <=m ; j++)
		{scanf("%d ",&p);
		if(p)
			fre[i][j] = true;
		}
		
	
memset(v[Ix][Iy],0,sizeof(v[Ix][Iy]));
p=1;
qx.push(Ix);
qy.push(Iy);

viz[Ix][Iy ] = true;

while(p){
X = qx.front();
Y = qy.front();

for(i = 0; i < 8 ; i++)
	if(isIn(X + di[i],Y + dj[i])) 
	{if(check(v[X+di[i]][Y+dj[i]],v[X][Y][dir[i]],dir[i]))
		{if(!viz[X + di[i]][ Y + dj[i]])
			{p++;
			viz[X + di[i]][ Y + dj[i]] = true;
			qx.push(X + di[i]);
			qy.push(Y + dj[i]);
			}
		}
	}
p--;
qx.pop();
qy.pop();
}


p = v[0][0][0];
for(i = 0 ; i < 8 ; i++)
	if(p > v[Fx][Fy][i])
		p = v[Fx][Fy][i];
	
if(p == v[0][0][0])
	printf("-1");
else
	printf("%d",p);

return 0;}