Cod sursa(job #505600)

Utilizator loginLogin Iustin Anca login Data 3 decembrie 2010 01:21:44
Problema Car Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 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], 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);
	p[ist][jst]=-1;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			b[i][j]=infinit;
	b[ist][jst]=0;
	int i, j, ii, jj;
	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];
			int c;
			if (p[i][j]==-1)c=0;
			else c=o[op[p[i][j]]][k];
			if (in_m (ii, jj) && !a[ii][jj] && b[i][j]+c<b[ii][jj])
			{
				b[ii][jj]=b[i][j]+c;
				p[ii][jj]=k;
				if (ii!=ifin || jj!=jfin)
				{
					Qi.push(ii);
					Qj.push(jj);
				}
			}
		}
	}
}

int main ()
{
	read ();
	init();
	solve ();
	ofstream fout ("car.out");
	fout<<b[ifin][jfin];
	return 0;
}