Cod sursa(job #844161)

Utilizator IliesiDanielDaniel IliesiDaniel Data 28 decembrie 2012 21:13:59
Problema Car Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <iostream>
#include <fstream>

using namespace std;

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

unsigned n, m, Si, Sj, Fi, Fj;
int Di[]={ -1, -1, -1,  0, 0,  1, 1, 1 };
int Dj[]={ -1,  0,  1, -1, 1, -1, 0, 1 };
int harta[505][505];
long mini=-1;

int detCost(int L, int C, int l, int c)
{
	if(l==0 && c==0 || L==l && C==c)	return 0;
	else	if( -L==l && -C==c)	return 4;

	if(L==1)	L=3;
		else	if(L==0)	L=2;
				else	L=1;

	if(C==1)	C=3;
		else	if(C==0)	C=2;
				else	C=1;

	if(l==1)	l=3;
		else	if(l==0)	l=2;
				else	l=1;

	if(c==1)	c=3;
		else	if(c==0)	c=2;
				else	c=1;

	l = L - l;
	c = C - c;

	if(l<0)	l=-l;
	if(c<0)	c=-c;

	if(l==0)	if(c==1)	return 1;
					else	if(c==2)	return 2;
							else;
		else	if(l==1)	if(c==0)	return 1;
								else	if(c==1)	return 2;
											else	if(c==2)	return 3;
													else;
					else	if(c==0)	return 2;
								else	return 3;

	return 2;
}

void cautare(int ci, int cj, int dl, int dc, long cost)
{
	int dir, l, c, tmp;

	if(ci==Fi && cj==Fj)	if(mini==-1)	mini=cost;
									else	if(mini > cost)	mini=cost;
											else;
	else	if( (mini!=-1 && cost<mini) || mini==-1 )
				for(dir=0; dir<8; ++dir)
				{
					l=ci+Di[dir];
					c=cj+Dj[dir];

					if(harta[l][c]==0)
					{
						harta[l][c]=1;

						tmp=detCost(l-ci, c-cj, dl, dc);
						cautare(l, c, l-ci, c-cj, cost+tmp);

						harta[l][c]=0;
					}
				}
}

int main(void)
{
	int i, j;
	fin>>n>>m>>Si>>Sj>>Fi>>Fj;

	for(i=1; i<=n; i++)
	{
		harta[i][0]=harta[i][m+1]=1;

		for(j=1; j<=m; j++)
			fin>>harta[i][j];
	}

	harta[1][1]=1;
	harta[0][0] = harta[n+1][0] = harta[0][m+1] = harta[n+1][m+1] = 1;
	for(j=1; j<=m; j++)
		harta[0][j]=harta[n+1][j]=1;

	cautare(Si, Sj, 0, 0, 0);

	fout<<mini;

	fin.close();
	fout.close();
	return 0;
}