Cod sursa(job #992669)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 2 septembrie 2013 12:31:22
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <fstream>

using namespace std;

int n,m,a[105][105],i,jj,lr,cr,lj,cj,r[105][105],j[105][105],minim=100000000,linie,coloana;
int dx[]={-1,-1,0,1,1,1,0,-1};
int dy[]={0,1,1,1,0,-1,-1,-1};

struct coord
{
	int lin,col;
};
coord q[50000];

inline void LeeRomeo()
{
	int pr,ul,x,y,xf,yf,k,val;
	pr=ul=1;
	q[1].lin=lr;
	q[1].col=cr;
	r[lr][cr]=1;
	while(pr<=ul)
	{
		x=q[pr].lin;
		y=q[pr].col;
		pr++;val=r[x][y];
		for(k=0;k<8;k++)
		{
			xf=x+dx[k];
			yf=y+dy[k];
			if(a[xf][yf]==1)
				if(r[xf][yf]==0 || r[xf][yf]>val+1)
				{
					r[xf][yf]=val+1;
					ul++;
					q[ul].lin=xf;
					q[ul].col=yf;
				}
		}
	}
}

inline void LeeJulieta()
{
	int pr,ul,x,y,xf,yf,k,val;
	pr=ul=1;
	q[1].lin=lj;
	q[1].col=cj;
	j[lj][cj]=1;
	while(pr<=ul)
	{
		x=q[pr].lin;
		y=q[pr].col;
		pr++;val=j[x][y];
		for(k=0;k<8;k++)
		{
			xf=x+dx[k];
			yf=y+dy[k];
			if(a[xf][yf]==1)
				if(j[xf][yf]==0 || j[xf][yf]>val+1)
				{
					j[xf][yf]=val+1;
					ul++;
					q[ul].lin=xf;
					q[ul].col=yf;
				}
		}
	}
}

inline void Solve()
{
	for(i=1;i<=n;i++)
		for(jj=1;jj<=m;jj++)
			if(r[i][jj]==j[i][jj] && r[i][jj]!=0 && r[i][jj]<minim)
			{
				minim=r[i][jj];
				linie=i;
				coloana=jj;
			}
}

int main()
{
	char c[210],caracter;
	ifstream fin ("rj.in");
	ofstream fout ("rj.out");
	fin>>n>>m;fin.get();
	for(i=1;i<=n;i++)
	{
		fin.getline(c, 200);
		for(jj=0;jj<m;jj++)
		{
			caracter=c[jj];
			if(caracter=='R')
			{
				lr=i;
				cr=jj+1;
			}
			else
				if(caracter=='J')
				{
					lj=i;
					cj=jj+1;
				}
				else
					if(caracter==' ')
						a[i][jj+1]=1;
					else
						a[i][jj+1]=0;
		}
	}
	LeeRomeo();
	LeeJulieta();
	/*for(i=1;i<=n;i++)
	{
		for(jj=1;jj<=m;jj++)
			fout<<r[i][jj]<<" ";
		fout<<"\n";
	}
	fout<<"\n";
	for(i=1;i<=n;i++)
	{
		for(jj=1;jj<=m;jj++)
			fout<<j[i][jj]<<" ";
		fout<<"\n";
	}
	fout<<"\n";*/
	Solve();
	fout<<minim<<" "<<linie<<" "<<coloana<<"\n";
	return 0;
}