Cod sursa(job #505848)

Utilizator loginLogin Iustin Anca login Data 4 decembrie 2010 11:06:26
Problema Car Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
# include <fstream>
# include <iostream>
# include <queue>
# include <algorithm>
# define infinit 2000000000
# define DIM 505
using namespace std;
int n, m, a[DIM][DIM], b[DIM][DIM], p[DIM][DIM][16], di[8]={-1, -1, 0, 1, 1, 1, 0, -1}, dj[8]={0, 1, 1, 1, 0, -1, -1, -1};
int ist, jst, ifin, jfin, o[10][10], op[8]={4,5,6,7,0,1,2,3};

void read ()
{
	ifstream fin ("car.in");
	fin>>n>>m>>ist>>jst>>ifin>>jfin;
	for(int i=1;i<=n;++i)
		for (int j=1;j<=m;++j)
			fin>>a[i][j];
}

void init ()
{
	for(int i=0;i<8;++i)
		for(int j=i;j<8;++j)
			if (j-i==4)o[i][j]=o[j][i]=0;
			else if ((j-i)%4==2)o[i][j]=o[j][i]=2;
			else if (j-i==5 || j-i==3)o[i][j]=o[j][i]=1;
			else if (i+1==j || (i==0 && j==7))o[i][j]=o[j][i]=3;
			else o[i][j]=o[j][i]=4;
}
					
int inline in_m (int i, int j)
{
	if (i && j && i<=n && j<=m)return 1;
	return 0;
}

void solve ()
{
	queue<int>Qi, Qj;
	Qi.push(ist);
	Qj.push(jst);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			if (!a[i][j])
				for(int k=0;k<8;++k)
					p[i][j][k]=infinit;
	p[ist][jst][1]=-1;
//	b[ist][jst]=0;
	int i, j, ii, jj, ad;
	while (Qi.size())
	{
		i=Qi.front();Qi.pop();
		j=Qj.front();Qj.pop();
		for(int k=0;k<8;++k)
		{
			ii=i+di[k];
			jj=j+dj[k];
			if (in_m (ii, jj) && !a[ii][jj])
			{
				ad=0;
				if (p[i][j][1]==-1)
					p[ii][jj][k]=0, ad=1;
				else
					for(int q=0;q<8;++q)
						if (p[i][j][q]<infinit && p[i][j][q]+o[op[q]][k]<p[ii][jj][k])
							p[ii][jj][k]=p[i][j][q]+o[op[q]][k], ad=1;
				if (ad && (ii!=ifin || jj!=jfin))
				{
					Qi.push(ii);
					Qj.push(jj);
				}	
			}
		}
	}
}

int main ()
{
	read ();
	init();
	solve ();
	ofstream fout ("car.out");
	int bst=infinit;
	for(int k=0;k<8;++k)
		if (p[ifin][jfin][k]<bst)
			bst=p[ifin][jfin][k];
	fout<<bst;
	return 0;
}