Cod sursa(job #404831)

Utilizator Mishu91Andrei Misarca Mishu91 Data 26 februarie 2010 19:23:04
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <fstream>
#include <stack>

using namespace std;

const int MAX_N = 505;
const int INF = 0x3f3f3f3f;

ifstream fin ("car.in");
ofstream fout ("car.out");

const int dx[] = {-1,-1, 0, 1, 1, 1, 0,-1},
	      dy[] = { 0, 1, 1, 1, 0,-1,-1,-1}; 

int N, M, Xs, Ys, Xf, Yf, A[MAX_N][MAX_N];
int D[(1 << 21) + 4];
stack <int> Q[2];

inline int code(int i, int j, int dir)
{
	return ((dir << 18) + (i << 9) + j);
}

void citire()
{
	fin >> N >> M >> Xs >> Ys >> Xf >> Yf;

	for(int i = 1; i <= N; ++i)
		for(int j = 1; j <= M; ++j)
			fin >> A[i][j];
}

bool expand(int ant)
{
	int j = (ant & 511), i = ((ant >> 9) & 511), dir = (ant >> 18);
	
	int act = code(i, j, (dir+1)&7);
	if(D[act] > D[ant]+1)
	{
		D[act] = D[ant]+1;
		Q[D[act]&1].push(act);
	}

	act = code(i, j, (dir+7)&7);
	if(D[act] > D[ant]+1)
	{
		D[act] = D[ant]+1;
		Q[D[act]&1].push(act);
	}

	i += dx[dir], j += dy[dir];
	if(i < 1 || i > N || j < 1 || j > M || A[i][j]) return 0;

	if(i == Xf && j == Yf) return 1;

	act = code(i, j, dir);
	if(D[act] > D[ant])
	{
		D[act] = D[ant];
		Q[D[act] & 1].push(act);
	}

	return 0;
}

void solve()
{
	memset(D, INF, sizeof D);
	for(int i = 0; i < 8; ++i)
	{
		int act = code(Xs, Ys, i);
		Q[0].push(act);
		D[act] = 0;
	}

	int Sol = 0;
	while(!Q[0].empty() || !Q[1].empty())
	{
		while(!Q[Sol&1].empty())
		{
			int act = Q[Sol & 1].top();
			Q[Sol & 1].pop();
			if(expand(act))
			{
				fout << Sol << "\n";
				return;
			}
		}
		++Sol;
	}

	fout << "-1\n";
}

int main()
{
	citire();
	solve();
}