Cod sursa(job #477814)

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

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

int main()

{
	int minc=200,minl=200,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]=b[i][0]=b[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]=b[0][j]=b[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,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 (b[lin+dx[j]][col+dy[j]]==0)
					{
						if (a[lin+dx[j]][col+dy[j]]==q) 
							if (lin+dx[j]<minl) minl=lin+dx[j],minc=col+dy[j]; else
								if ((lin+dx[j]==minl) && (col+dy[j]<minc)) minc=col+dy[j]; 
					
						
						b[lin+dx[j]][col+dy[j]]=q,jx.push_back(lin+dx[j]),jy.push_back(col+dy[j]),++ju2;
					}
					
			jx.pop_front();jy.pop_front();
		}
		if (minl<200) {printf("%d %d %d",q,minl,minc);return 0;}
		ju=ju2;
	}
	
}