Cod sursa(job #614525)

Utilizator simaghitaSima Gheorghe Eugen simaghita Data 6 octombrie 2011 19:23:41
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
#include<fstream>
using namespace std;
int a[105][105],R[105][105],J[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[20000];

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;	}
	}
	fin.close();
}
inline bool Interior(int x, int y)
{
	return(1<=x && x<=L && 1<=y && y<=C);
}

void Bordare()
{
	int i,j,n,m;
	n = L + 1;
	m = C + 1;
	for(i=1; i<=L; i++)
		for(j=1; j<=C; j++)
			R[i][j] = J[i][j] = 1000000;
}

void LeeRomeo()
{
	int pr,ul,i,j,x,y,k,cost=0;
	pr = ul = 0;
	
	q[ul].x = xr;
	q[ul].y = yr;
	R[xr][yr]=1;
	while(pr<=ul)
	{
		x=q[pr].x;
		y=q[pr].y;
		cost=R[x][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 && cost+1 < R[i][j])
				{
					ul++;
					q[ul].x=i;
					q[ul].y=j;
					R[i][j]=cost+1;
				}
			}
		}
	}
	
}
void LeeJulieta()
{
	int pr,ul,i,j,x,y,k,cost=0;
	pr = ul = 0;
	
	q[ul].x = xj;
	q[ul].y = yj;
	J[xj][yj]=1;
	while(pr<=ul)
	{
		x=q[pr].x;
		y=q[pr].y;
		cost=J[x][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 && cost+1 < J[i][j])
				{
					ul++;
					q[ul].x=i;
					q[ul].y=j;
					J[i][j]=cost+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(R[i][j]==J[i][j])
				if(R[i][j] < tmin)
				{
					tmin=R[i][j];
					c1=i; c2=j;
				}
				else 
					if(R[i][j]==tmin)
					{
						c1=min(c1,i);
						c2=min(c2,j);
					}
				
		}
	fout<<tmin<<" "<<c1<<" "<<c2<<"\n";
	fout.close();
}

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