Cod sursa(job #828409)

Utilizator ChallengeMurtaza Alexandru Challenge Data 3 decembrie 2012 18:59:56
Problema Car Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include <fstream>
#include <queue>

using namespace std;

const char InFile[]="car.in";
const char OutFile[]="car.out";
const int MaxN=503;
const int dx[]={1, 1, 0, -1, -1, -1,  0,  1};
const int dy[]={0, 1, 1,  1,  0, -1, -1, -1};
const int DIR=8;
const int INF=1<<30;

ifstream fin(InFile);
ofstream fout(OutFile);

struct Node
{
	Node(int x=0, int y=0, int dir=0):x(x),y(y),dir(dir){}

	inline void Move()
	{
		x+=dx[dir];
		y+=dy[dir];
	}

	inline void RotateCW()
	{
		dir+=7;
		dir%=DIR;
	}

	inline void RotateCCW()
	{
		++dir;
		dir%=DIR;
	}

	int x,y,dir;
};

int N,M,A[MaxN][MaxN],sol,D[MaxN][MaxN][DIR],stx,sty,sfx,sfy,curr;
char expanded[MaxN][MaxN][DIR];
queue<Node> Q[2];

inline void Update(const Node &from, const Node &to, const int &cost)
{
	if(!A[to.x][to.y] && D[to.x][to.y][to.dir]>D[from.x][from.y][from.dir]+cost)
	{
		D[to.x][to.y][to.dir]=D[from.x][from.y][from.dir]+cost;
		Q[curr^cost].push(to);
	}
}

int main()
{
	fin>>N>>M;
	fin>>stx>>sty>>sfx>>sfy;
	for(register int i=1;i<=N;++i)
	{
		for(register int j=1;j<=M;++j)
		{
			fin>>A[i][j];
		}
	}
	fin.close();

	for(register int i=0;i<=N+1;++i)
	{
		A[i][0]=A[i][M+1]=1;
	}
	for(register int j=0;j<=M+1;++j)
	{
		A[0][j]=A[N+1][j]=1;
	}

	for(register int i=1;i<=N;++i)
	{
		for(register int j=1;j<=N;++j)
		{
			for(register int d=0;d<DIR;++d)
			{
				D[i][j][d]=INF;
			}
		}
	}

	for(register int d=0;d<DIR;++d)
	{
		D[stx][sty][d]=0;
		Q[0].push(Node(stx,sty,d));
	}

	curr=0;
	while(!Q[curr].empty())
	{
		while(!Q[curr].empty())
		{
			Node nod=Q[curr].front();
			Q[curr].pop();
			if(expanded[nod.x][nod.y][nod.dir])
			{
				continue;
			}
			if(nod.x==sfx && nod.y==sfy)
			{
				sol=D[sfx][sfy][nod.dir];
				goto afis;
			}
			Node to=nod; to.Move();
			Update(nod,to,0);
			to=nod; to.RotateCW();
			Update(nod,to,1);
			to=nod; to.RotateCCW();
			Update(nod,to,1);
		}
		curr^=1;
	}

afis:
	fout<<sol;
	fout.close();
	return 0;
}