Cod sursa(job #204837)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 27 august 2008 13:51:57
Problema Car Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <stdio.h>

int n, m, xs, ys, xd, yd, a[505][505];
int dx[8] = {0,1,1,1,0,-1,-1,-1}, dy[8] = {1,1,0,-1,-1,-1,0,1};

typedef struct
{
   int x, y, d;
} Coada;
Coada c[5000055];

void citire()
{
	freopen("car.in","r",stdin);
	freopen("car.out","w",stdout);

	int i, j;
	scanf("%d %d",&n,&m);
	scanf("%d %d %d %d",&xs,&ys,&xd,&yd);

	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= m; j++) 
		{
			scanf("%d",&a[i][j]);
			if (a[i][j]) a[i][j] = -1;
			else a[i][j] = -2;
		}
		a[i][0] = a[i][m + 1] = -1;
	}
	for (i = 1; i <= m; i++) a[0][i] = a[n + 1][i] = -1;
	a[0][0] = a[0][m + 1] = a[n + 1][0] = a[n + 1][m + 1] = -1;
}

int aflu_unghi(int a, int b)
{
	if (a == b) return 0;
	if (a - b == 1 || b - a == 1 || (a == 7 && b == 0) || (b == 7 && a == 0)) return 1;
	if (a - b == 2 || b - a == 2 || (a == 6 && b == 0) || (b == 6 && a == 0) || (a == 7 && b == 1) || (b == 7 && a == 1)) return 2;
	return -1;
}

void Lee()
{
	int p, u, i, xx, yy, unghi;
	c[1].x = xs; c[1].y = ys;
        a[xs][ys] = 0;
	p = u = 1;
	for (i = 0; i < 8; i++)
	{
		xx = c[1].x + dx[i];
		yy = c[1].y + dy[i];
		if (a[xx][yy] != -1)
		{
			c[++u].x = xx;
			c[u].y = yy;
			c[u].d = i;
			a[xx][yy] = 0;
			if (xx == xd && yy == yd) return;
		}
	}
	p++;
	while (p <= u)
	{
		for (i = 0; i < 8; i++)
		{
			xx = c[p].x + dx[i];
			yy = c[p].y + dy[i];

			if (a[xx][yy] != -1)
			{
				unghi = aflu_unghi(c[p].d, i);
				if ((a[xx][yy] == -2 || a[xx][yy] >= a[c[p].x][c[p].y] + unghi) && unghi != -1)
				{
					c[++u].x = xx;
					c[u].y = yy;
					c[u].d = i;
					a[xx][yy] = a[c[p].x][c[p].y] + unghi;
				}
			}
		}
		p++;
	}
}

int main()
{
	citire();
	Lee();
	printf("%d\n",a[xd][yd]);
	return 0;
}