Cod sursa(job #287994)

Utilizator zalmanDanci Emanuel Sebastian zalman Data 25 martie 2009 14:01:14
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
// romeo & juliet, infoarena, 25.03.09
#include <stdio.h>
#include <values.h>
#include <string.h>
#define NMAX 102

int romeo[NMAX][NMAX], juliet[NMAX][NMAX], xr, yr, xj, yj, N, M;
int dl[]={-1, -1, -1, 0, 1, 1,  1,  0};
int dc[]={-1,  0,  1, 1, 1, 0, -1, -1};
char s[NMAX], ch;
struct coada{int x, y;};


void read(void)
{
	freopen("rj.in", "r", stdin);
	scanf("%d %d", &N, &M);
	scanf("%c", &ch);
	for(register int i = 1; i <= N; i++)
	{
		gets(s);
		for(register int k = 0; k < strlen(s); k++)
		{
		 if( s[k] == 'X')
		  romeo[i][k+1] = juliet[i][k+1] = -1;
		 if( s[k] == 'R')
			{
			 xr = i;
			 yr = k + 1;
			}
		 if( s[k] == 'J')
		  {
			xj = i;
			yj = k+1;
		  }
		}

	}
	fclose(stdin);
}
int inside(int x, int y)
{
	if( !x || !y)
	 return 0;
	if( x > N )
	 return 0;
	if( y > M)
	 return 0;

 return 1;
}
void lee(int a[][NMAX], int ii, int jj)
{
	int prim, ultim, li, ci;
	coada c[NMAX*NMAX+1], p;
	prim = ultim = 1;
	c[prim].x = ii;
	c[prim].y = jj;
	a[ii][jj] = 1;

	while(prim <= ultim)
	{
		p = c[prim++];
		for(int i = 0; i < 8; i++)
		{
		 li = p.x + dl[i];
		 ci = p.y + dc[i];
		 if(inside(li, ci) && (!a[li][ci]))
			{
			 a[li][ci] = a[p.x][p.y] + 1;
			 ++ultim;
			 c[ultim].x = li;
			 c[ultim].y = ci;
			}
		}
	}
}
void solve(void)
{
	lee(romeo, xr, yr);
	lee(juliet, xj, yj);
}
void print(void)
{
	freopen("rj.out", "w", stdout);
	int tmin, x, y;
	tmin = x = y = MAXINT;
	for(int i = 1; i <= N; i++)
		for(int j = 1; j <= M; j++)
		 if((romeo[i][j] == juliet[i][j]) && (romeo[i][j] > 0))
		  if (tmin > romeo[i][j])
		  {
			tmin = romeo[i][j];
			x = i;
			y = j;
		  }

	printf("%d %d %d", tmin, x, y);
	fclose(stdout);

}

int main(void)
{
	read();
	solve();
	print();

	return 0;
}