Cod sursa(job #700625)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 1 martie 2012 11:14:31
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <fstream>

using namespace std;

int n, m, xr, yr, xj, yj, minim = 2000000000, xmin, ymin;
char a[105][105];
int R[105][105], J[105][105];
int A[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int B[] = {0, 1, 1, 1, 0, -1, -1, -1};
struct coord
{
	int x, y;
};
coord q[10005];

void Read()
{
	ifstream f("rj.in");
	f>>n>>m;
	int i;
	for (i=1; i<=n; i++)
		f>>(a[i] + 1);
	f.close();
}

void Bordare()
{
	int n1, i, m1;
	n1 = n + 1;
	m1 = m + 1;
	for (i = 0; i <= n1; i++)
		a[i][0] = a[i][m1] = 'X';
	for (i = 0; i <= m1; i++)
		a[0][i] = a[n1][i] = 'X';
}

void Initializare()
{
	int i, j, n1 = n + 1, m1 = m + 1;
	for (i = 0; i<=n1; i++)
		for (j=0; j<=m1; j++)
			R[i][j] = J[i][j] = 2000000000;
}

void Cautare()
{
	int i, j;
	for (i=1; i<=n; i++)
		for (j=1; j<=m; j++)
		{	
			if (a[i][j] == 'R')
			{
				xr = i;
				yr = j;
			}
			if (a[i][j] == 'J')
			{
				xj = i;
				yj = j;
			}
		}
}

void Romeo()
{
	int pr, ul, x, y, i, j, k, d;
	pr = 0;
	ul = -1;
	ul++;
	q[ul].x = xr;
	q[ul].y = yr;
	R[xr][yr] = 0;
	while (pr<=ul)
	{
		x = q[pr].x;
		y = q[pr].y;
		d = R[x][y];
		pr++;
		for (k = 0; k<8; k++)
		{
			i = x + A[k];
			j = y + B[k];
			if (a[i][j]!='X' && d + 1 < R[i][j])
			{
				R[i][j] = d + 1;
				ul++;
				q[ul].x = i;
				q[ul].y = j;
			}
		}
	}
}

void Julieta()
{
	int pr, ul, x, y, i, j, k, d;
	pr = 0;
	ul = -1;
	ul++;
	q[ul].x = xj;
	q[ul].y = yj;
	J[xj][yj] = 0;
	while (pr<=ul)
	{
		x = q[pr].x;
		y = q[pr].y;
		d = J[x][y];
		pr++;
		for (k = 0; k<8; k++)
		{
			i = x + A[k];
			j = y + B[k];
			if (a[i][j]!='X' && d + 1 < J[i][j])
			{
				J[i][j] = d + 1;
				ul++;
				q[ul].x = i;
				q[ul].y = j;
			}
		}
	}
}

void Suprapunere()
{
	int i, j;
	for (i=1; i<=n; i++)
		for (j=1; j<=m; j++)
			if (R[i][j] == J[i][j] && R[i][j] < minim)
			{
				minim = R[i][j];
				xmin = i;
				jmin = j;
			}
}

int Solve()
{
	Bordare();
	Initializare();
	Cautare();
	Romeo();
	Julieta();
	Suprapunere();
}

void Write()
{
	ofstream g("rj.out");
	g<<minim<<" "<<xmin<<" "<<ymin<<"\n";
	g.close();
}

int main()
{
	Read();
	Solve();
	Write();
	return 0;
}