Cod sursa(job #559200)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 17 martie 2011 17:56:44
Problema Car Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 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;
int A[maxn][maxn],D[maxn][maxn],P[maxn][maxn],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]);
}

int mod(int x)
{
	return x<0 ? -x : x;
}

void drum()
{
	int d,dir,c;
	for(i=1;i<=N;i++)
		for(j=1;j<=M;j++)
				D[i][j]=oo;
	D[Si][Sj]=0;
	Qi.push(Si); Qj.push(Sj); v[Si][Sj]=1;
	for(;!Qi.empty();Qi.pop(),Qj.pop())
	{
		i=Qi.front(); j=Qj.front();
		if(i==Fi && j==Fj) break;
		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]>N) continue;
			dir= d>4 ? d-4 : d;
			if(mod(dir-P[i][j])%4==1) c=1;
			if(dir%2==P[i][j]%2) c=2;
			if(dir==P[i][j] || (i==Si && j==Sj)) c=0;
			
			if(D[i][j]+c<D[i+dx[d]][j+dy[d]])
			{
				D[i+dx[d]][j+dy[d]]=D[i][j]+c;
				P[i+dx[d]][j+dy[d]]=dir;
				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();
	printf("%d",D[Fi][Fj]);
}