Cod sursa(job #82373)

Utilizator flionIonescu Ionut Florin flion Data 6 septembrie 2007 19:13:16
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <stdio.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()
{
	freopen("rj.in", "r", stdin);
	freopen("rj.out", "w", stdout);

	// decodific matricea
	for (scanf("%d%d", &N, &M), i = 1; i <= N; i++)
		for (scanf("%c", &c), j = 1; j <= M; j++)
		{
			scanf("%c", &c);

			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;
				}
			}
		}

	// 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;
				}
			}

	printf("%d %d %d\n", minim-1, xf, yf);

	return 0;
}