Cod sursa(job #257873)

Utilizator ciorile.chioareBogatu Adrian ciorile.chioare Data 14 februarie 2009 10:31:35
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
//rj

#include <stdio.h>
#define N 110
#define M 110


int n,m;

int v1[N][M];
int v2[N][M];

int R[2],J[2];

int ci,cj;

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

int p,u;

void citire()
{
	int i,j;
	char s[M];
	scanf("%d%d\n",&n, &m);
	for(i=1;i<=n;++i)
	{
		/*
		for(j=1;j<=m;++j)
		{
			scanf("%c",&c);
			
			if(c=='R')
			{
				R[0]=i;
				R[1]=j;
				v1[i][j]=1;
			}
			
			if(c=='J')
			{
				J[0]=i;
				J[1]=j;
				v2[i][j]=1;
			}
			
			if(c=='X')
				v1[i][j]=-1;
		}
		scanf("%c",&c);
		*/
		gets(s);
		for(j=0 ; s[j] ; ++j)
		{
			if(s[j]=='R')
			{
				R[0]=i;
				R[1]=j+1;
				v1[i][j+1]=1;
			}
			
			if(s[j]=='J')
			{
				J[0]=i;
				J[1]=j+1;
				v2[i][j+1]=1;
			}
			
			if(s[j]=='X')
				v1[i][j+1]=-1;
		}
	}
	
}

void bord()
{
	for(int i=0;i<=n+1;++i)
	{
		v1[i][0]=v1[i][n+1]=-1;
	}
	
	for(int i=0;i<=m+1;++i)
	{
		v1[0][i]=v1[m+1][i]=-1;
	}
	
}

void bfs(int x0[2], int V[N][M])
{
	int i,q[N*M][2];
	int x[2],y[2];
	p=0;
	u=0;
	q[u][0]=x0[0];
	q[u][1]=x0[1];
	u++;
	
	while(p!=u)
	{
		x[0]=q[p][0];
		x[1]=q[p][1];
		p++;
		for(i=0;i<8;++i)
		{
			y[0]=x[0]+dx[i];
			y[1]=x[1]+dy[i];
			if(V[y[0]][y[1]]==0)
			{
				q[u][0]=y[0];
				q[u][1]=y[1];
				u++;
				V[y[0]][y[1]]=1+V[x[0]][x[1]];
			}
		}
	}
}

void copie()
{
	for(int i=0;i<=n+1;++i)
		for(int j=0;j<=m+1;++j)
		{
			if( (v2[i][j]!=1)&&(v1[i][j]!=1) )
				v2[i][j]=v1[i][j];
			if(v2[i][j]==1)
				v1[i][j]=-1;
			if(v1[i][j]==1)
				v2[i][j]=-1;
		}
}
	
int comp()
{
	int tmin=99999;
	
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			if( (v1[i][j]==v2[i][j])&&(v1[i][j]<tmin)&&(v1[i][j]>0) )
			{
				tmin=v1[i][j];
				ci=i;
				cj=j;
			}
	return tmin;
}

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

int main()
{
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	
	citire();
	bord();
	copie();
	//afisare(v1);
	bfs(R,v1);
	bfs(J,v2);
	//afisare(v1);
	//printf("\n");
	//afisare(v2);
	
	int a=comp();
	printf("%d %d %d", a,ci,cj);
	return 0;
}