Cod sursa(job #820010)

Utilizator dariusdariusMarian Darius dariusdarius Data 19 noiembrie 2012 22:26:13
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
int r[105][105],jl[105][105];
int dx[]={0,-1,-1,0,1,1,1,0,-1};
int dy[]={0,0,1,1,1,0,-1,-1,-1};
struct STRUCT {int x,y;};
queue<STRUCT> q;
STRUCT temp,rom,jul;
char s[105];
int u;
int  main()
{
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	int n,m,i,j;
	char ch;
	scanf("%d%d\n",&n,&m);
	for(i=0;i<=n+1;i++)
		r[i][0]=r[i][m+1]=jl[i][0]=jl[i][m+1]=-1;
	for(j=0;j<=m+1;j++)
		r[0][j]=r[n+1][j]=jl[0][j]=jl[n+1][j]=-1;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			r[i][j]=jl[i][j]=-2;
	for(i=1;i<=n;i++)
	{
	gets(s);
	u=strlen(s);
	if(u<m)
		while(u<m)
		{
			strcat(s," ");
			u++;
		}
	for(j=0;j<u;j++)
	{
		ch=s[j];
		if(ch=='R')
			{r[i][j+1]=1;rom.x=i;rom.y=j+1;}
		if(ch=='J')
			{jl[i][j+1]=1;jul.x=i;jul.y=j+1;}
		if(ch==' ')
			continue;
		if(ch=='X')
			r[i][j+1]=jl[i][j+1]=-1;
	}
	}
	//Lee pentru Romeo:
	temp.x=rom.x;
	temp.y=rom.y;
	q.push(temp);
	while(!q.empty())
	{
		for(i=1;i<=8;i++)
		{
			temp.x=q.front().x+dx[i];
			temp.y=q.front().y+dy[i];
			if(r[temp.x][temp.y]==-2)
				{q.push(temp);r[temp.x][temp.y]=r[q.front().x][q.front().y]+1;}
		}
		q.pop();
	}
	while(!q.empty())
		q.pop();
	//Lee pentru Julieta:
	temp.x=jul.x;
	temp.y=jul.y;
	q.push(temp);
	while(!q.empty())
	{
		for(i=1;i<=8;i++)
		{
			temp.x=q.front().x+dx[i];
			temp.y=q.front().y+dy[i];
			if(jl[temp.x][temp.y]==-2)
				{q.push(temp);jl[temp.x][temp.y]=jl[q.front().x][q.front().y]+1;}
		}
		q.pop();
	}
	//Finalizare:
	STRUCT min;
	int mm=1000000000;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			if(r[i][j]==jl[i][j] && r[i][j]!=-1 && r[i][j]!=-2)
				if(r[i][j]<mm)
				{mm=r[i][j];min.x=i;min.y=j;}

	printf("%d %d %d",mm,min.x,min.y);
	return 0;
}