Cod sursa(job #154)

Utilizator wefgefAndrei Grigorean wefgef Data 5 decembrie 2006 22:15:17
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <cstdio>

using namespace std;

#define Nmax 512

const int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1},
		  dy[8]	= {0, 1, 1, 1, 0, -1, -1, -1};
int n, m, xf, yf, xs, ys, rez, v[2][512*1024], l[2], min[1<<22];
char a[Nmax][Nmax], viz[1<<22];

void readdata()
{
	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, &xf, &yf);
	for (i = 1; i <= n; ++i)
	for (j = 1; j <= m; ++j)
		scanf("%d", &a[i][j]);
}

void solve()
{
	int i, cont, p, p2, j, k, dir, nr, ii, jj, poz;
	
	for (i = 0; i < 8; ++i)
	{
		poz = i + (ys << 3) + (xs << 12);
		v[0][++l[0]] = poz;
		min[poz] = 1;
		viz[poz] = 1;
	}
	
	p = 0;
	while (l[p])
	{
		p2 = 1-p;
		for (k = 1; k <= l[p]; ++k)
		if (viz[v[p][k]] == 1)
		{
			nr = v[p][k];
			dir = nr & 7;
			j = (nr & (511 << 3)) >> 3;
			i = (nr & (511 << 12)) >> 12;
			
			//inainteaza
			ii = i + dx[dir];
			jj = j + dy[dir];
			poz = (ii << 12) + (jj << 3) + dir;
			if (ii > 0 && ii <= n && jj > 0 && jj <= m)			
			if (!a[ii][jj])
			if (viz[poz] == 0 || min[poz] > min[nr])
			{
				viz[poz] = 1;
				min[poz] = min[nr];
				v[p][++l[p]] = poz;
			}
			
			//miscare clokwise
			dir = dir+1; if (dir == 8) dir = 0;
			ii = i;
			jj = j;
			poz = (ii << 12) + (jj << 3) + dir;
			if (ii > 0 && ii <= n && jj > 0 && jj <= m)			
			if (!a[ii][jj])
			if (viz[poz] == 0)
			{
				viz[poz] = 1;
				min[poz] = min[nr] + 1;
				v[p2][++l[p2]] = poz;
			}		
			
			//miscare anti-clokwise
			dir = dir-2; if (dir == -1) dir = 7;
			ii = i;
			jj = j;
			poz = (ii << 12) + (jj << 3) + dir;
			if (ii > 0 && ii <= n && jj > 0 && jj <= m)			
			if (!a[ii][jj])
			if (viz[poz] == 0)
			{
				viz[poz] = 1;
				min[poz] = min[nr] + 1;
				v[p2][++l[p2]] = poz;
			}
			
			if (i == xf && j == yf)
			{
				rez = min[nr];
				return;
			}
			viz[nr] = 2;
		}
		l[p] = 0;
		p = p2;
	}
}

void writedata()
{
	printf("%d\n", rez-1);
}

int main()
{
	readdata();
	solve();
	writedata();
	return 0;
}