Cod sursa(job #82378)

Utilizator flionIonescu Ionut Florin flion Data 6 septembrie 2007 19:24:22
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <fstream.h>

#define nmax 105

int R[nmax][nmax];

int J[nmax][nmax];

int A[nmax][nmax];

int X[nmax * nmax];

int Y[nmax * nmax];

int N, M, i, j, l, r, x, y, m, xr, yr, xj, yj, xf, yf, minim;

char c;

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

int main()
{
	ifstream fin("rj.in");
	ofstream fout("rj.out");

	// decodific matricea
	fin>>N>>M;

	fin.get(c);

	for (i = 1; i <= N; ++i)
	{
		for (fin.get(c), j = 1; j <= M && c != '\n'; ++j)
		{
			switch(c)
			{
				case 'R':
				{
					A[i][j] = 1;
					xr = i;
					yr = j;
					break;
				}
				case 'J':
				{
					A[i][j] = 1;
					xj = i;
					yj = j;
					break;
				}
				case ' ':
				{
					A[i][j] = 1;
					break;
				}
			}

			fin.get(c);
		}

		for (; j <= M; ++j)
			A[i][j] = 1;
	}

	// il parcurg pe romeo
	for (X[l = 1] = xr, Y[r = 1] = yr, R[xr][yr] = 1; l <= r; ++l)
	{
		x = X[l];
		y = Y[l];

		for (i = 0; i < 4; i++)
			if (A[x + dx[i]][y + dy[i]] == 1
			&& !R[x + dx[i]][y + dy[i]])
			{
				++r;
				X[r] = x + dx[i];
				Y[r] = y + dy[i];
				R[X[r]][Y[r]] = 1 + R[x][y];
			}
	}

	// o parcurg pe julieta
	for (X[l = 1] = xj, Y[r = 1] = yj, J[xj][yj] = 1; l <= r; ++l)
	{
		x = X[l];
		y = Y[l];

		for (i = 0; i < 4; i++)
			if (A[x + dx[i]][y + dy[i]] == 1
			&& !J[x + dx[i]][y + dy[i]])
			{
				++r;
				X[r] = x + dx[i];
				Y[r] = y + dy[i];
				J[X[r]][Y[r]] = 1 + J[x][y];
			}
	}

	// pargurg matricea rezultat si gasesc minimul
	for (i = N, minim = N*M+1; i; i--)
		for (j = M; j; j--)
			if (A[i][j] == 1 && R[i][j] && J[i][j] && R[i][j] % 2 == J[i][j] % 2)
			{
				m = R[i][j] > J[i][j]? R[i][j]: J[i][j];
				if (m <= minim)
				{
					minim = m;
					xf = i;
					yf = j;
				}
			}

	fout<<minim-1<<' '<<xf<<' '<<yf<<'\n';

	return 0;
}