Cod sursa(job #325974)

Utilizator pcinfoCarmen Popescu pcinfo Data 23 iunie 2009 10:43:29
Problema Car Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <fstream>
#include <queue>

using namespace std;

ifstream f("car.in");
ofstream g("car.out");

const int dx[8]={-1,-1,-1,0,0,1,1,1};
const int dy[8]={-1,0,1,-1,1,-1,0,1};
const int cost[8][8]={{0,1,2,1,3,2,3,4},{1,0,1,2,2,3,4,3},{2,1,0,3,1,4,3,2},{1,2,3,4,3,2,1},{3,2,1,4,0,3,2,1},{2,3,4,1,3,0,1,2},{3,4,3,2,2,1,0,1},{4,3,2,3,1,2,1,0}};
const int INF=2000000;
int m,n;
int a[501][501];
int t[501][501],dir[501][501];;

int ok(int i,int j)
{
	if (a[i][j]==1)
		return 0;
	if (i<=0)
		return 0;
	if (i>m)
		return 0;
	if (j<=0)
		return 0;
	if (j>n)
		return 0;
	return 1;
}

struct nod {
	int x,y,d;
};

int main()
{
	queue<nod> q;
	nod nd,nd1;
	int i0,j0,i1,j1,i,j,d,c;
	
	
	f>>m>>n>>i0>>j0>>i1>>j1;
	for (i=1;i<=m;i++)
		for (j=1;j<=n;j++)
		{
			f>>a[i][j];
			t[i][j]=INF;
			dir[i][j]=-1;
		}
	
		
	t[i0][j0]=0;
	
	for (d=0;d<8;d++)
	{
		i=i0+dx[d];
		j=j0+dy[d];
		if (ok(i,j))
		{
			t[i][j]=0;
			dir[i][j]=d;
			nd.x=i; nd.y=j; nd.d=d;
			q.push(nd);
		}
	}
		
	while (!q.empty())
	{
		nd=q.front();
		q.pop();
		
		for (d=0;d<8;d++)
		{
			i=nd.x+dx[d];
			j=nd.y+dy[d];
			if (ok(i,j))
			{
				c=t[nd.x][nd.y]+cost[nd.d][d];
				if (c<t[i][j])
				{
					t[i][j]=c;
					dir[i][j]=d;
					nd1.x=i; nd1.y=j; nd1.d=d;
					q.push(nd1);
				}
				else
					if (c==t[i][j] && d!=dir[i][j])
					{
						dir[i][j]=d;
						nd1.x=i; nd1.y=j; nd1.d=d;
						q.push(nd1);
					}
			}
		}
	}
	
	if (dir[i1][j1]==-1)
		g<<-1;
	else
		g<<t[i1][j1];
	f.close();
	g.close();
	return 0;
}