Cod sursa(job #411976)

Utilizator RegeleUmbrelorPopescu Mihai RegeleUmbrelor Data 5 martie 2010 11:49:02
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
using namespace std;
#include<fstream>
const int MAX=105,v[]={-1,-1,0,1,1,1,0,-1},o[]={0,-1,-1,-1,0,1,1,1};
int n,m,ro[MAX][MAX],ju[MAX][MAX],minpoz,xr,yr,xj,yj,coada[MAX*MAX][2],cod[MAX*MAX][2],cpy[MAX*MAX][2];
char c;
void citire()
{
	int i,j;
	ifstream in("rj.in",ifstream::in);
	in>>n>>m;
	in.get();
	for(i=1;i<=n;++i)
	{	
		for(j=1;j<=m;++j)
		{	
			c=in.get();
			if(c=='X')
				ro[i][j]=ju[i][j]=-1;
			if(c=='R')
			{	
				xr=i;
				yr=j;
				ro[i][j]=ju[i][j]=-1;
			}
			if(c=='J')
			{
				xj=i;
				yj=j;
				ro[i][j]=ju[i][j]=-1;
			}
		}
		in.get();
	}
	for(i=0;i<=n+1;++i)
		ro[i][0]=ro[i][m+1]=ju[i][0]=ju[i][m+1]=-1;
	for(j=0;j<=n+1;++j)
		ro[0][j]=ro[n+1][j]=ju[0][j]=ju[n+1][j]=-1;
	in.close();
}

void pas( int &lm1, int &lm2)
{
	int u=0,i,xd,yd,d=ro[cod[u][0]][cod[u][1]];
	for(i=0;i<lm1;++i)
		for(int k=0;k<8;++k)
		{	
			xd=cod[i][0]+v[k];
			yd=cod[i][1]+o[k];
			if(ro[xd][yd]!=-1 &&ro[xd][yd]!=d+1)
			{	
				ro[xd][yd]=d+1;
				cpy[u][0]=xd;cpy[u++][1]=yd;
			}
		}
	lm1=u;
	for(i=0;i<lm1;++i)
	{	
		cod[i][0]=cpy[i][0];cod[i][1]=cpy[i][1];
	}
	u=0;
	for(i=0;i<lm2;++i)
		for(int k=0;k<8;++k)
		{	
			xd=coada[i][0]+v[k];
			yd=coada[i][1]+o[k];
			if(ju[xd][yd]!=-1 &&ju[xd][yd]!=d+1)
			{	
				ju[xd][yd]=d+1;
				cpy[u][0]=xd;cpy[u++][1]=yd;
			}
		}
	lm2=u;
	for(i=0;i<lm2;++i)
	{	
		coada[i][0]=cpy[i][0];coada[i][1]=cpy[i][1];
	}
}
void rez()
{
	int i,t=0,u1=1,u2=1,a,b;
	cod[0][0]=xr;cod[0][1]=yr;ro[xr][yr]=1;
	coada[0][0]=xj;coada[0][1]=yj;ju[xj][yj]=1;
	while(!t)
	{
		pas(u1,u2);
		for(i=0;i<u2;++i)
		{
			a=ro[coada[i][0]][coada[i][1]];
			b=ju[coada[i][0]][coada[i][1]];
			if(a==b && a>0)
			{	
				minpoz=a;
				cpy[t][0]=coada[i][0];
				cpy[t++][1]=coada[i][1];
			}
		}
	}
	xr=cpy[0][0];yr=cpy[0][1];
	for(i=1;i<t;++i)
		if(cpy[i][0]<xr || (cpy[i][0]==xr && cpy[i][1]<yr))
		{	
			xr=cpy[i][0];
			yr=cpy[i][1];
		}
	ofstream out("rj.out",ofstream::out);
	out << minpoz<<" "<<xr<<" "<<yr;
	out.close();

}

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