Cod sursa(job #412356)

Utilizator RegeleUmbrelorPopescu Mihai RegeleUmbrelor Data 5 martie 2010 15:22:53
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
using namespace std;
#include<stdio.h>
const int MAX=105;
int a[MAX][MAX],b[MAX][MAX],coada[10005][2],m,n,xr,yr,xj,yj;
char oras[MAX][MAX];

void citire()
{
	int i,j;char *s,c;
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	scanf("%d%d", &n, &m);
	scanf("%c",&c);
	for(i=1;i<=n;++i)
	{	
		s=oras[i]+1;
		gets(s);
		for(j=1;j<=m;++j)
		{	
			if(oras[i][j]=='X')
				a[i][j]=b[i][j]=-1;
			if(oras[i][j]=='R') 
			{	
				a[i][j]=b[i][j]=1;
				xr=i;yr=j;
			}
			if(oras[i][j]=='J')
			{	
				a[i][j]=b[i][j]=1;
				xj=i;yj=j;
			}
		}
	}
	for(i=0;i<=n+1;++i)
		a[i][0]=a[i][m+1]=b[i][0]=b[i][m+1]=-1;
	for(j=0;j<=m+1;++j)
		a[0][j]=a[n+1][j]=b[0][j]=b[n+1][j]=-1;
}


void bfs(int x1, int y1, int me[MAX][MAX])
{
	int u=0,p=0,x2,y2,i;
	const int dl[]={-1,-1,0,1,1,1,0,-1},dcol[]={0,-1,-1,-1,0,1,1,1,0};
	coada[u][0]=x1;coada[u++][1]=y1;
	while(p!=u)
	{	
		for(i=0;i<8;++i)
		{
			x2=coada[p][0]+dl[i];y2=coada[p][1]+dcol[i];
			if( !me[x2][y2])
			{
				coada[u][0]=x2;
				coada[u++][1]=y2;
				me[x2][y2]=me[coada[p][0]][coada[p][1]]+1;
			}
		}
		p++;
	}
}
	


void rez()
{
	int min=10001,xf,yf,i,j;
	bfs(xr,yr, a);
	bfs(xj,yj, b);
	for(i=1;i<=n;++i)
		for(j=1;j<=m;++j)
			if(a[i][j]==b[i][j] && a[i][j]<min && a[i][j]>1)
			{	
				min=a[i][j];
				xf=i; yf=j;
			}
	printf("%d %d %d",min,xf,yf);
}

int main()
{
	citire();
	rez();
	return 0;
}