Cod sursa(job #477803)

Utilizator c_adelinaCristescu Adelina c_adelina Data 16 august 2010 13:12:48
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <cstdio>
#include <deque>
using namespace std;

deque <int> rx,ry,jx,jy;
int a[104][104];

int main()

{
	int minc=10000000,minl=0,ro=1,ro2,ju2,ju=1,lin,col,i,j,n,m,q,dx[]={-1,-1,0,1,1,1,0,-1},dy[]={0,1,1,1,0,-1,-1,-1};
	char s[104];
	
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	scanf("%d %d\n",&n,&m);
	for (i=1;i<=n;++i)
		{
		 a[i][0]=a[i][m+1]=-1;	
		 gets(s);
         for (j=0;j<m;++j) 
		 if (s[j]=='X') a[i][j+1]=-1; else
			 if (s[j]=='R') rx.push_back(i),ry.push_back(j+1); else
				 if (s[j]=='J') jx.push_back(i),jy.push_back(j+1);
		}
	for (j=0;j<m+2;++j)	a[0][j]=a[n+1][j]=-1;
	for (q=2;;++q)
	{
		for (ro2=ju2=0,i=1;i<=ro;++i)
		{
			if (a[rx.front()][ry.front()]>-1)
				for (j=0,lin=rx.front(),col=ry.front();j<8;++j)
					if ((a[lin+dx[j]][col+dy[j]]>=0) && (a[lin+dx[j]][col+dy[j]]!=q))
						a[lin+dx[j]][col+dy[j]]=q,rx.push_back(lin+dx[j]),ry.push_back(col+dy[j]),++ro2;
					
			rx.pop_front();ry.pop_front();
		}
		ro=ro2;
		for (i=1;i<=ju;++i)
		{
			if (a[jx.front()][jy.front()]>-1)
				for (j=0,lin=jx.front(),col=jy.front();j<8;++j)
					if (a[lin+dx[j]][col+dy[j]]>=0) 
						{if (a[lin+dx[j]][col+dy[j]]==q)
						{if (minc>col+dy[j]) minc=col+dy[j],minl=lin+dx[j];}
								 else
							if  (a[lin+dx[j]][col+dy[j]]!=q*2)
							a[lin+dx[j]][col+dy[j]]=q*2,jx.push_back(lin+dx[j]),jy.push_back(col+dy[j]),++ju2; 
						}
	
								
							
					
			jx.pop_front();jy.pop_front();
		}
		if (minl) {printf("%d %d %d",q,minl,minc);return 0;}
		ju=ju2;
	}
	
}