Cod sursa(job #280020)

Utilizator 0000go gcc 0000 Data 13 martie 2009 10:11:55
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <stdio.h>

#define IN "rj.in"
#define OUT "rj.out"
#define N_MAX 1<<7

int tip,N,M;
int A[1<<7][1<<7],B[1<<7][1<<7];
char sir[1<<7];
struct que{int f,s;} Q[1<<13];
que r,jj;

const int xx[]={-1,-1,-1,0,0,1,1,1};
const int yy[]={-1,0,1,-1,1,-1,0,1};

void scan()
{
	freopen(IN,"r",stdin);
	freopen(OUT,"w",stdout);

	scanf("%d%d\n",&N,&M);
	int i,j;

	for(i=1;i<=N;++i)
	for(j=1;j<=M;++j)
		A[i][j] = B[i][j] = 10101;

	for(i=1;i<=N;++i)
	{
		fgets(sir,1<<7,stdin);
		for(j=0;j<M;++j)
		{
			if(sir[j] == 'X')
			       A[i][j+1] = B[i][j+1] = -1;
			if(sir[j] == 'R')
			       r.f = i,r.s = j+1;
			if(sir[j] == 'J')
			       jj.f = i,jj.s = j+1;
		}

	}
}

int ok(int x,int y,int c)
{
	if(x <0 || x>N || y<0 || y>M)
		return 0;
	if(!tip && A[x][y] <= c)
		return 0;
	if(tip && B[x][y] <= c)
		return 0;
	return 1;
}

void bf(que S)
{
	int i,j,last = 0;
	Q[++last] = S;


	for(i=1;i<=last;++i)
	{
		int x = Q[i].f;
		int y = Q[i].s;
		int c = tip?B[x][y]+1:A[x][y]+1;

		for(j=0;j<8;++j)
			if( ok(x+xx[j],y+yy[j],c) )
			{
				Q[++last].f = x+xx[j];
				Q[  last].s = y+yy[j];

				if(!tip)
					A[x+xx[j]][y+yy[j]] = c;
				else
				       B[x+xx[j]][y+yy[j]] = c;
			}
	}
}

void solve()
{
	A[r.f][r.s] = 0;
	B[jj.f][jj.s] = 0;

	tip = 0;
	bf(r);
	tip = 1;
	bf(jj);

	int i,j;
	que rez;
	rez.s = rez.f = 0;
	A[0][0] = 10101;

	for(i=1;i<=N;++i)
	for(j=1;j<=M;++j)
		if(A[i][j] == B[i][j] && A[rez.f][rez.s] > A[i][j] && A[i][j] != -1)
			rez.f = i,rez.s = j;
	printf("%d %d %d\n",A[rez.f][rez.s]+1,rez.f,rez.s);

}

int main()
{
	scan();
	solve();
	return 0;
}