Cod sursa(job #559275)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 17 martie 2011 18:57:29
Problema Car Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <stdio.h>
#define maxn 505
#define oo 200000000
#include <queue>
using namespace std;

const int dx[9]={0,0,1,1,1,0,-1,-1,-1};
const int dy[9]={0,1,1,0,-1,-1,-1,0,1};
int i,j,N,M,Si,Sj,Fi,Fj,R;
int A[maxn][maxn],D[maxn][maxn][9],v[maxn][maxn];
queue<int> Qi,Qj;

void citire()
{
	scanf("%d %d",&N,&M);
	scanf("%d %d %d %d",&Si,&Sj,&Fi,&Fj);
	for(i=1;i<=N;i++)
		for(j=1;j<=M;j++)
			scanf("%d",&A[i][j]);
}

inline int mod(int x)
{
	return x<0 ? -x : x;
}
inline int min(int a, int b)
{
	return a<b ? a : b;
}

void drum()
{
	int d,dir,c;
	for(i=1;i<=N;i++)
		for(j=1;j<=M;j++)
			for(dir=1;dir<=8;dir++)
				D[i][j][dir]=oo;
	for(dir=1;dir<=8;dir++)	D[Si][Sj][dir]=0;
	Qi.push(Si); Qj.push(Sj); v[Si][Sj]=1;
	for(;!Qi.empty();Qi.pop(),Qj.pop())
	{
		i=Qi.front(); j=Qj.front();
		for(dir=1;dir<=8;dir++)
		for(d=1;d<=8;d++)
		{
			if(A[i+dx[d]][j+dy[d]]==1) continue;
			if(i+dx[d]<1 || i+dx[d]>N || j+dy[d]<1 || j+dy[d]>M) continue;
			
			c=7;
			if(mod(d-dir)%8==1) c=1;
			if(mod(d-dir)%4==2) c=2;
			if(d==dir) c=0;
			if(c==7) continue;
			if(D[i][j][dir]+c<D[i+dx[d]][j+dy[d]][d])
			{
				D[i+dx[d]][j+dy[d]][d]=D[i][j][dir]+c;
				if(!v[i+dx[d]][j+dy[d]])
				{
					v[i+dx[d]][j+dy[d]]=1;
					Qi.push(i+dx[d]);
					Qj.push(j+dy[d]);
				}
			}
		}
		v[i][j]=0;
	}
}

int main()
{
	freopen("car.in","r",stdin);
	freopen("car.out","w",stdout);
	citire();
	drum();
	R=oo;
	for(i=1;i<=8;i++)
		R=min(R,D[Fi][Fj][i]);
	printf("%d",R);
}