Cod sursa(job #673275)

Utilizator Lokycatalin petre Loky Data 4 februarie 2012 11:10:52
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.48 kb
#include <cstdio>
#include <cstring>

using namespace std;

bool ok;
long int i,j,n,m,s1[10005],s2[10005],a[103][103],b[103][103],p,r,inc,sf,sf1,x,y,minim,nr;
char s[105];

int main()
{
	freopen ("rj.in","r",stdin);
	freopen ("rj.out","w",stdout);
	scanf("%d%d \n",&n,&m);
	for (i=1;i<=n;i++) {
		gets(s);
		for (j=0;j<=m-1;j++) {
			if (s[j]=='X') {a[i][j+1]=-1;b[i][j+1]=-1;}
			if (s[j]=='R') {s1[1]=i;s2[1]=j+1;a[i][j+1]=-1;b[i][j+1]=-1;}
			if (s[j]=='J') {p=i;r=j+1;a[i][j+1]=-1;b[i][j+1]=-1;}
		}
	}
	for (i=0;i<=n+1;i++) {
		a[i][0]=-1;
		a[i][m+1]=-1;
		b[i][0]=-1;
		b[i][m+1]=-1;
	}
	for (i=0;i<=m+1;i++) {
		a[0][i]=-1;
		a[n+1][i]=-1;
		b[0][i]=-1;
		b[n+1][i]=-1;
	}
	
	ok=true;
	inc=1;sf=1;sf1=1;nr=1;
	while (ok==true) {
		ok=false;
		nr++;
		for (i=inc;i<=sf;i++) {
			x=s1[i];
			y=s2[i];
			if (a[x][y+1]==0) {sf1++;s1[sf1]=x;s2[sf1]=y+1;ok=true;a[x][y+1]=nr;}
			if (a[x][y-1]==0) {sf1++;s1[sf1]=x;s2[sf1]=y-1;ok=true;a[x][y-1]=nr;}
			if (a[x+1][y]==0) {sf1++;s1[sf1]=x+1;s2[sf1]=y;ok=true;a[x+1][y]=nr;}
			if (a[x-1][y]==0) {sf1++;s1[sf1]=x-1;s2[sf1]=y;ok=true;a[x-1][y]=nr;}
			if (a[x+1][y+1]==0) {sf1++;s1[sf1]=x+1;s2[sf1]=y+1;ok=true;a[x+1][y+1]=nr;}
			if (a[x-1][y-1]==0) {sf1++;s1[sf1]=x-1;s2[sf1]=y-1;ok=true;a[x-1][y-1]=nr;}
			if (a[x+1][y-1]==0) {sf1++;s1[sf1]=x+1;s2[sf1]=y-1;ok=true;a[x+1][y-1]=nr;}
			if (a[x-1][y+1]==0) {sf1++;s1[sf1]=x-1;s2[sf1]=y+1;ok=true;a[x-1][y+1]=nr;}
		}
		inc=sf+1;
		sf=sf1;
	}
	
	s1[1]=p;s2[1]=r;
	
	ok=true;
	inc=1;sf=1;sf1=1;nr=1;
	while (ok==true) {
		ok=false;
		nr++;
		for (i=inc;i<=sf;i++) {
			x=s1[i];
			y=s2[i];
			if (b[x][y+1]==0) {sf1++;s1[sf1]=x;s2[sf1]=y+1;ok=true;b[x][y+1]=nr;}
			if (b[x][y-1]==0) {sf1++;s1[sf1]=x;s2[sf1]=y-1;ok=true;b[x][y-1]=nr;}
			if (b[x+1][y]==0) {sf1++;s1[sf1]=x+1;s2[sf1]=y;ok=true;b[x+1][y]=nr;}
			if (b[x-1][y]==0) {sf1++;s1[sf1]=x-1;s2[sf1]=y;ok=true;b[x-1][y]=nr;}
			if (b[x+1][y+1]==0) {sf1++;s1[sf1]=x+1;s2[sf1]=y+1;ok=true;b[x+1][y+1]=nr;}
			if (b[x-1][y-1]==0) {sf1++;s1[sf1]=x-1;s2[sf1]=y-1;ok=true;b[x-1][y-1]=nr;}
			if (b[x+1][y-1]==0) {sf1++;s1[sf1]=x+1;s2[sf1]=y-1;ok=true;b[x+1][y-1]=nr;}
			if (b[x-1][y+1]==0) {sf1++;s1[sf1]=x-1;s2[sf1]=y+1;ok=true;b[x-1][y+1]=nr;}
		}
		inc=sf+1;
		sf=sf1;
	}
	
	minim=20005;
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
			if (a[i][j]==b[i][j] &&a[i][j]<minim &&a[i][j]>0) {minim=a[i][j];p=i;r=j;}
			
	printf("%d %d %d",minim ,p ,r);
	
			
	fclose(stdin);
	fclose(stdout);
	return 0;
}