Cod sursa(job #1165840)

Utilizator enedumitruene dumitru enedumitru Data 2 aprilie 2014 23:16:04
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include<fstream>
#include<queue>
using namespace std;
ifstream f("rj.in"); ofstream g("rj.out");
int dl[]={-1,-1,-1,0,1,1,1,0};
int dc[]={-1,0,1,1,1,0,-1,-1};
struct art {int x,y;};
int n,m,rx,ry,jx,jy,A[102][102],B[102][102];
queue <art> R,J;
inline void Read_Data()
{	char c;
	f>>n>>m; f.get(c);
	int i,j;
	for(i=1;i<=n;i++)
	{	for(j=1;j<=m;j++)
		{	f.get(c);
			if(c=='X') A[i][j]=B[i][j]=1;
			else if(c=='R') rx=i, ry=j, A[i][j]=B[i][j]=1;
			else if(c=='J') jx=i, jy=j, A[i][j]=B[i][j]=1;
		}
		f.get(c);
	}
	for(i=0; i<=n+1; i++) A[i][0]=A[i][m+1]=B[i][0]=B[i][m+1]=1;
	for(j=0; j<=m+1; j++) A[0][j]=A[n+1][j]=B[0][j]=B[n+1][j]=1;
}
inline void Solve()
{	int l,c,ll,cc,k,i,j;
	art aux; aux.x=rx; aux.y=ry; R.push(aux);
	while(!R.empty())
	{	l=R.front().x; c=R.front().y; R.pop();
		for(k=0;k<=7;k++)
		{	ll=l+dl[k];cc=c+dc[k];
			if(!A[ll][cc])
			{	A[ll][cc]=A[l][c]+1;
				aux.x=ll; aux.y=cc; R.push(aux);
			}
		}
	}
	aux.x = jx; aux.y = jy; J.push(aux);
	while(!J.empty())
	{	l=J.front().x; c=J.front().y; J.pop();
		for(k=0;k<=7;k++)
		{	ll=l+dl[k]; cc=c+dc[k];
			if(!B[ll][cc])
			{	B[ll][cc]=B[l][c]+1;
				aux.x = ll; aux.y = cc; J.push(aux);
			}
		}
	}
	int minim=232556544,sol1,sol2;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			if(A[i][j]==B[i][j] && A[i][j]<minim && A[i][j]>1) minim=A[i][j], sol1 = i, sol2 = j;
		g<<minim<<" "<<sol1<<" "<<sol2<< '\n';
}
int main()
{	Read_Data(); Solve();
	g.close();	return 0;
}