Cod sursa(job #440568)

Utilizator ooctavTuchila Octavian ooctav Data 12 aprilie 2010 09:24:37
Problema Car Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <queue>
using namespace std;
const int NMAX = 501;
const int MMAX = 501;
const int INF = 1000000000;
const int lin[] = {0, -1, -1, 0, 1, 1, 1, 0, -1};
const int col[] = {0, 0, 1, 1, 1, 0, -1, -1, -1};
int N, M;
pair<int, int> S;
pair<int, int> D;
bool C[NMAX][MMAX];
int A[NMAX][MMAX][9];
queue<int> Q;

void citire()
{
	scanf("%d%d", &N, &M);
	scanf("%d%d%d%d", &S.first, &S.second, &D.first, &D.second);
	for(int i = 1 ; i <= N ; i++)
		for(int j = 1 ; j <= M ; j++)
			scanf("%d", &C[i][j]);
}

void init()
{
	for(int i = 1 ; i <= N ; i++)
		for(int j = 1 ; j <= M ; j++)
			for(int k = 1 ; k <= 8 ; k++)
				A[i][j][k] = INF;
			
	for(int k = 1 ; k <= 8 ; k++)
		A[S.first][S.second][k] = 0;
}


inline int dec(int x, int y)
{
	if(x > y)
		swap(x, y);
	if(y - x <= 2)
		return (y - x);
	if(x + 8 - y <= 2)
		return (x + 8 - y);
	return 0;
}

inline int incad(int x, int y)
{
	return(x && x <= N && y && y <= M);
}

void BFS()
{
	int x, i, j, dir;
	for(int k = 1 ; k <= 8 ; k++)
		Q.push((S.first<<9) + S.second + (k<<18));
	while(!Q.empty())
	{
		x = Q.front();
		i = (x>>9) & 511;
		j = x & 511;
		dir = (x>>18);
		for(int k = 1 ; k <= 8 ; k++)
			if(dec(k, dir) <= 2 && !C[i + lin[k]][j + col[k]] && incad(i + lin[k], j + col[k]))
				if(A[i][j][dir] + dec(k, dir) < A[i + lin[k]][j + col[k]][k])
				{
					A[i + lin[k]][j + col[k]][k] = A[i][j][dir] + dec(k, dir);
					Q.push(((i+lin[k])<<9) + (j+col[k]) + (k<<18));
				}
		Q.pop();
	}
}

void scrie()
{
	int minim = INF;
	for(int k = 1 ; k <= 8 ; k++)
		minim = min(minim, A[D.first][D.second][k]);
	printf("%d\n",minim);
}

int main()
{
	freopen("car.in","r",stdin);
	freopen("car.out","w",stdout);
	citire();
	init();
	BFS();
	scrie();
	return 0;
}