Cod sursa(job #117484)

Utilizator vlad.maneaVlad Manea vlad.manea Data 21 decembrie 2007 16:02:50
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <stdio.h>
#define infinit 32767

int maxim(int a, int b)
{
	if (a > b) return a;
	return b;
}

int N, M, i, j, xr, yr, xj, yj, x, y, min, ic, sc, max, fx, fy;

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

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

char S[105][105], c;

int RO[105][105], JU[105][105], X[10005], Y[10005];

void read();
void solve();
void write();

int main()
{
	read();

	solve();

	write();

	return 0;
}

void read()
{
	freopen("rj.in", "r", stdin);
	scanf("%d%d\n", &N, &M);

	for (i = 0; i <= N+1; ++i)
		for (j = 0; j <= M+1; ++j)
			RO[i][j] = JU[i][j] = infinit;

	for (i = 1; i <= N; i++)
	{
		S[i][0] = 'X';
		gets(S[i]+1);

		for (j = 1; j <= M; j++)
		{
			if (S[i][j] == 'R')
				xr = i, yr = j;
			else if (S[i][j] == 'J')
				xj = i, yj = j;
		}

//		scanf("\n", &c);
	}
}

void write()
{
	freopen("rj.out", "w", stdout);
	printf("%d %d %d\n", min, fx, fy);
}

void solve()
{
	// bordez coloanele

	for (i = 0; i <= N+1; i++)
		S[i][0] = S[i][M+1] = 'X';

	for (j = 0; j <= M+1; j++)
		S[0][j] = S[N+1][j] = 'X';

	// fac lee pentru romeo

	for (RO[xr][yr] = 1, X[ic] = xr, Y[ic] = yr; ic <= sc; ++ic)
	{
		x = X[ic];
		y = Y[ic];

		for (i = 0; i < 8; ++i)
		{
			if (S[x + dx[i]][y + dy[i]] != 'X' && RO[x+dx[i]][y+dy[i]] > 1 + RO[x][y])
			{
				++sc;
				X[sc] = x + dx[i];
				Y[sc] = y + dy[i];
				RO[X[sc]][Y[sc]] = RO[x][y] + 1;
			}
		}
	}

	for (JU[xj][yj] = 1, ic = sc = 0, X[ic] = xj, Y[ic] = yj; ic <= sc; ++ic)
	{
		x = X[ic];
		y = Y[ic];

		for (i = 0; i < 8; ++i)
		{
			if (S[x + dx[i]][y + dy[i]] != 'X' && JU[x+dx[i]][y+dy[i]] > 1 + JU[x][y])
			{
				++sc;
				X[sc] = x + dx[i];
				Y[sc] = y + dy[i];
				JU[X[sc]][Y[sc]] = JU[x][y] + 1;
			}
		}
	}

	for (min = infinit, x = 1; x <= N; ++x)
		for (y = 1; y <= M; ++y)
			if (S[x][y] != 'X' && RO[x][y] == JU[x][y] && RO[x][y] < min)
			{
				min = JU[x][y];
				fx = x;
				fy = y;
			}
}