Cod sursa(job #80024)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 25 august 2007 14:30:32
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <cstdio>
#define fin  "rj.in"
#define fout "rj.out"
#define Nmax 101

#define DBGx
#define FL

int N,M;
char buff[128];
int xr,yr,xj,yj;
int R[Nmax][Nmax],J[Nmax][Nmax];

int st,dr,a[Nmax*Nmax],b[Nmax*Nmax];

void ext(int x,int y,int cst,int c[][Nmax])
{
	if (c[x][y] || x<1 || x>N || y<1 || y>M)
	       return ;
	c[x][y]=cst+1;
	++dr;
	a[dr]=x;
	b[dr]=y;	
}

void go(int c[][Nmax])
{
	int i,tmp,x,y,cst;

	tmp=dr;

	for (i=st;i<=tmp;++i)
	{
		x=a[i]; y=b[i];
		cst=c[x][y];
		ext(x+1,y,cst,c); ext(x+1,y+1,cst,c);
		ext(x,y+1,cst,c); ext(x-1,y+1,cst,c);
		ext(x-1,y,cst,c); ext(x-1,y-1,cst,c);
		ext(x,y-1,cst,c); ext(x+1,y-1,cst,c);
	}

	st=tmp+1;

	if (st<=dr)
		go(c);
}

void bf(int x,int y,int c[][Nmax])
{
	st=1; dr=1;
	a[1]=x; 
	b[1]=y;
	
	c[x][y]=1;

	go(c);
}

int main()
{
	int i,j,k;
	int ret,x,y;

	freopen(fin,"r",stdin);
#ifdef FL
	freopen(fout,"w",stdout);
#endif

	scanf("%d%d",&N,&M);

	i=1; j=1;

	for (;;)
	{
		fread(buff,1,128,stdin);
		for (k=0;k<128;++k)
		{
			if (buff[k]=='R')
			{
				xr=i; yr=j;
				++j;
			}
			if (buff[k]=='J')
			{
				xj=i; yj=j;
				++j;
			}
			if (buff[k]==' ')
				++j;
			if (buff[k]=='X')
			{
				J[i][j]=R[i][j]=Nmax*Nmax;
				++j;
				
			}
			if (j==M+1)
			{
				++i;
				j=1;
			}
			if (i>N)
				break;
		}
		if (i>N)
			break;
	}

#ifdef DBG
	for (i=1;i<=N;++i)
	{
		for (j=1;j<=M;++j)
			printf("%d ",R[i][j]);
		printf("\n");
	}
	printf("\n");
#endif
	
	bf(xr,yr,R);
	bf(xj,yj,J);

#ifdef DBG
	for (i=1;i<=N;++i)
	{
		for (j=1;j<=M;++j)
			printf("%d ",R[i][j]);
		printf("\n");
	}
	printf("\n");
	for (i=1;i<=N;++i)
	{
		for (j=1;j<=M;++j)
			printf("%d ",J[i][j]);
		printf("\n");
	}
	printf("\n");
#endif

	ret=Nmax*Nmax;

	for (i=1;i<=N;++i)
	for (j=1;j<=M;++j)
		if (R[i][j]==J[i][j] && R[i][j]<ret && R[i][j])
		{
			ret=R[i][j];
			x=i; y=j;
		}

	printf("%d %d %d\n",ret,x,y);

	return 0;
}