Cod sursa(job #407631)

Utilizator brainwashed20Alexandru Gherghe brainwashed20 Data 2 martie 2010 15:10:15
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 kb
#include<stdio.h>
#include<string.h>

#define N 3000
#define M 101

int dx[]={-1,-1,-1,0,0,1,1,1};
int dy[]={-1,0,1,-1,1,-1,0,1};

struct punct { int x,y; } cd[N];

int p,nrelem,rom[M][M],jul[M][M],n,m;
char s[M];

void init() { p=nrelem=0; }

int vplin()
{
	if(nrelem==N) return 1;
	return 0;
}

int vgol()
{
	if(nrelem==0) return 1;
	return 0;
}

int add(punct x)
{
	if(vplin()==1) return 0;
	cd[(p+nrelem)%N]=x;
	nrelem++;
	return 1;
}

int extract(punct &x)
{
	if(vgol()==1) return 0;
	x=cd[p];
	nrelem--;
	p=(p+1)%N;
	return 1;
}

void lee(int a[M][M], punct pi, punct pf)
{
	int i;
	punct c1,c2;
	init();
	add(pi);
	while(vgol()==0)
	{
		extract(c1);
		for(i=0; i<8; i++)
		{
			c2.x=c1.x+dx[i];
			c2.y=c1.y+dy[i];
			if(a[c2.x][c2.y]==0)
			{
				a[c2.x][c2.y]=a[c1.x][c1.y]+1;
				add(c2);
				if(c2.x==pf.x && c2.y==pf.y) return;
			}
		}
	}
}

void afismat(int a[M][M])
{
	int i,j;
	for(i=0; i<=n+1; i++)
	{
		for(j=0; j<=m+1; j++)
			printf("%d ",a[i][j]);
		printf("\n");
	}
	printf("\n");
}

int main()
{
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	
	punct ri,ji;
	int i,j,imin=101,jmin=101,min=100000000;
	scanf("%d %d",&n,&m);
	gets(s);
	for(i=1; i<=n; i++)
	{
		gets(s);
		for(j=0; j<strlen(s); j++)
			if(s[j]=='X') rom[i][j+1]=jul[i][j+1]=-1;
			else if(s[j]=='R') rom[i][j+1]=1, ri.x=i, ri.y=j+1;
			else if(s[j]=='J') jul[i][j+1]=1, ji.x=i, ji.y=j+1;
	}
	for(i=0; i<=n+1; i++) rom[i][0]=-1, rom[i][m+1]=-1, jul[i][0]=-1, jul[i][m+1]=-1;
	for(i=0; i<=m+1; i++) rom[0][i]=-1, rom[n+1][i]=-1, jul[0][i]=-1, jul[n+1][i]=-1;
	lee(rom,ri,ji);
	lee(jul,ji,ri);
	//afismat(rom);
	//afismat(jul);
	for(i=1; i<=n; i++)
	for(j=1; j<=m; j++)
		if(rom[i][j]==jul[i][j] && jul[i][j]<min && jul[i][j]>0) min=jul[i][j], imin=i, jmin=j;
		else 
			if(rom[i][j]==jul[i][j] && jul[i][j]==min && jul[i][j]>0)
			{
				if(i<imin) i=imin, j=jmin;
				else if(i==imin && j<jmin) i=imin, j=jmin;
			}
	printf("%d %d %d",min,imin,jmin);
	return 0;
}