Cod sursa(job #614748)

Utilizator simaghitaSima Gheorghe Eugen simaghita Data 7 octombrie 2011 17:00:29
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include<fstream>
using namespace std;
int a[105][105],b[105][105],L,C,xr,yr,xj,yj;
short dx[] = {-1,1, 0,0,-1,-1, 1,1};
short dy[] = { 0,0,-1,1,-1, 1,-1,1};
struct coord
{
	int x,y;
};
coord q[11000];

void Citire()
{
	int i,j;
	char s[100];
	ifstream fin("rj.in");
	
	fin>>L>>C;
	fin.get();
	
	for(i=1; i<=L; i++)
	{
		fin.getline(s,100);
		for(j=0; j<C; j++)
			
			if(s[j]==' ')	a[i][j+1] = 0;
			else if(s[j]=='X')	a[i][j+1] = 1;
			else if(s[j]=='R')	{	xr = i;	yr = j+1; }
			else	{	xj = i;	yj = j+1;	}
	}
	for(i=1;i<=L;i++)
		for(j=1;j<=C;j++)
			b[i][j]=a[i][j];
	fin.close();
}
inline bool Interior(int x, int y)
{
	return(1<=x && x<=L && 1<=y && y<=C);
}

void LeeRomeo()
{
	int pr=0,ul=0,i,j,x,y,k;
	a[xr][yr]=2;
	q[ul].x = xr;
	q[ul].y = yr;
	while(pr<=ul)
	{
		x=q[pr].x;
		y=q[pr].y;
		pr++;
		if(Interior(x,y))
		{
			for(k=0;k<8;k++)
			{	
				i=x+dx[k];
				j=y+dy[k];
				if(a[i][j]==0)
				{
					ul++;
					q[ul].x=i;
					q[ul].y=j;
					a[i][j]=a[x][y]+1;
				}
			}
		}
	}
	
}
void LeeJulieta()
{
	int pr=0,ul=0,i,j,x,y,k;
	b[xj][yj]=2;
	q[ul].x = xj;
	q[ul].y = yj;
	while(pr<=ul)
	{
		x=q[pr].x;
		y=q[pr].y;
		pr++;
		if(Interior(x,y))
		{
			for(k=0;k<8;k++)
			{	
				i=x+dx[k];
				j=y+dy[k];
				if(b[i][j]==0)
				{
					ul++;
					q[ul].x=i;
					q[ul].y=j;
					b[i][j]=b[x][y]+1;
				}
			}
		}
	}
	
}


void Afisare()
{
	int i,j,tmin=1000000,c1=0,c2=0;
	ofstream fout("rj.out");
	for(i=1;i<=L;i++)
		for(j=1;j<=C;j++)
		{
			if(a[i][j]==b[i][j] && a[i][j] >1)
				if(tmin>a[i][j]-1)
				{
					tmin=a[i][j]-1;
					c1=i;
					c2=j;
				}
				
		}
	fout<<tmin<<" "<<c1<<" "<<c2<<"\n";
	fout.close();
}

int main ()
{
	Citire();
	LeeRomeo();
	LeeJulieta();
	Afisare();
	return 0;
}