Cod sursa(job #80623)

Utilizator DITzoneCAdrian Diaconu DITzoneC Data 28 august 2007 21:09:19
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

#define nmax 256
#define FOR(i,s,d) for(i=(s);i<(d);++i)
#define inf 1000111000
#define pb push
#define mp make_pair
#define f first
#define s second

int n,m,A[nmax][nmax],sol,B[nmax][nmax],pozx,pozy;
char H[nmax][nmax];
queue < pair <int,int> > Q;

void test(int i,int j,int ii,int jj)
{
	if(ii<0||jj<0||ii>=n||jj>=m||A[i][j]+1>=A[ii][jj])
		return ;
	A[ii][jj]=A[i][j]+1;
	Q.pb(mp(ii,jj));	
}

void doit(int ii,int jj)
{
	pair <int,int> x;
	int i,j;
	FOR(i,0,n) FOR(j,0,m)
	{
		A[i][j]=inf;
		if(H[i][j]=='X')
			A[i][j]=-1;
	}
	A[ii][jj]=1;
	Q.pb(mp(ii,jj));
	while(!Q.empty())
	{
		x=Q.front(), Q.pop();
		test(x.f,x.s,x.f,x.s+1);
		test(x.f,x.s,x.f,x.s-1);
		test(x.f,x.s,x.f+1,x.s);
		test(x.f,x.s,x.f-1,x.s);
		test(x.f,x.s,x.f-1,x.s-1);
		test(x.f,x.s,x.f-1,x.s+1);
		test(x.f,x.s,x.f+1,x.s-1);
		test(x.f,x.s,x.f+1,x.s+1);
	}
}

int main()
{
	int ii,i,j;
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	fgets(H[0],nmax,stdin);
	sscanf(H[0],"%d %d",&n,&m);
	FOR(i,0,n)
		fgets(H[i],nmax,stdin);
	FOR(i,0,n) FOR(j,0,n)
		if(H[i][j]=='R')
			doit(i,j);
	memcpy(B,A,sizeof(A));
	FOR(i,0,n) FOR(j,0,n)
		if(H[i][j]=='J')
			doit(i,j);
	sol=inf;
	FOR(i,0,n) FOR(j,0,n)
		if(A[i][j]==B[i][j]&&A[i][j]!=-1&&sol>A[i][j])
			sol=A[i][j],pozx=i,pozy=j;
	printf("%d %d %d\n",sol,pozx+1,pozy+1);
	return 0;
}