Cod sursa(job #505311)

Utilizator cioboata.iCioboata Ioan Liviu cioboata.i Data 1 decembrie 2010 18:07:57
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include<stdio.h>

const int N=1<<7;

int dlin[]={1,-1,0,0,1,1,-1,-1};
int dcol[]={0,0,1,-1,-1,1,-1,1};

struct punct
{
	int lin,col;
};

punct romeo,julieta,q[N*N];

int a[N][N],ajul[N][N],ibun,jbun,min=N*N,n,m;
char b[N][N];

void lee(punct start,int mat[N][N])
{
	int p,u,c,xn,yn;
	p=u=1;
	q[p].lin=start.lin;
	q[p].col=start.col;
	while(p<=u)
	{
		for(c=0;c<=7;c++)
		{
			xn=dlin[c]+q[p].lin;
			yn=dcol[c]+q[p].col;
			if(mat[xn][yn]==0)
			{
				mat[xn][yn]=mat[q[p].lin][q[p].col]+1;
				q[++u].lin=xn;
				q[u].col=yn;
			}
		}
		p++;
	}
}

void rezultat()
{
	int i,j;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		{
			if(a[i][j]==ajul[i][j] && a[i][j]>0)
			{
				if(min>a[i][j])
				{	
					min=a[i][j];
					ibun=i;
					jbun=j;
				}
			}
		}
	return ;
	
}

int main()
{
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	int i,j;
	scanf("%d%d\n",&n,&m);
	for(i=0;i<=n+1;i++)
	{
		a[i][0]=-1;
		a[i][n+1]=-1;
	}
	for(i=0;i<=m+1;i++)
	{
		a[0][i]=-1;
		a[n+1][i]=-1;
	}
	for(i=1;i<=n;i++)
		gets(&b[i][1]);
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		{
			if(b[i][j]=='R') { romeo.lin=i; romeo.col=j; a[i][j]=0; }
			else if (b[i][j]=='J') { julieta.lin=i; julieta.col=j; a[i][j]=0; }
			else if (b[i][j]=='X') a[i][j]=-1;
			else a[i][j]=0;
		}
	for(i=0;i<=n+1;i++)
		for(j=0;j<=m+1;j++)
			ajul[i][j]=a[i][j];
	lee(romeo,a);
	/*for(i=1;i<=n;i++)
	{	
		for(j=1;j<=m;j++)
			printf("%3d ",a[i][j]);
		printf("\n");
	}
	printf("\n");*/
	lee(julieta,ajul);
	/*for(i=1;i<=n;i++)
	{	
		for(j=1;j<=m;j++)
			printf("%3d ",ajul[i][j]);
		printf("\n");
	}*/
	
	rezultat();
	printf("%d %d %d",min+1,ibun,jbun);
	return 0;
}