Cod sursa(job #411542)

Utilizator RegeleUmbrelorPopescu Mihai RegeleUmbrelor Data 4 martie 2010 22:59:03
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
using namespace std;
#include<fstream>
const int MAX=105,v[4]={-1,0,1,0},o[4]={0,-1,0,1};
int n,m,ro[MAX][MAX],ju[MAX][MAX],coada[MAX*MAX][2],minpoz,xr,yr,xj,yj;
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;
			}
			if(c=='J')
			{
				xj=i;
				yj=j;
			}
		}
		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 bfs(int x, int y, int mat[MAX][MAX])
{
	int i,u=0,p=0,xd,yd;
	coada[u][0]=x;
	coada[u++][1]=y;
	while(u!=p)
	{	
		for(i=0;i<=3;++i)
		{
			xd=coada[p][0]+v[i];
			yd=coada[p][1]+o[i];
			if(mat[xd][yd]==0 && (xd!=x || yd!=y))
			{	
				mat[xd][yd]=mat[coada[p][0]][coada[p][1]]+1;
				coada[u][0]=xd;
				coada[u++][1]=yd;
			}
		}
		p++;
	}
}
	


void rez()
{
	int i,j;
	bfs(xr,yr, ro);
	bfs(xj,yj, ju);
	minpoz=MAX*MAX;
	for(i=1;i<=n;++i)
		for(j=1;j<=m;++j)
			if(ro[i][j]==ju[i][j] && ro[i][j]>0 && ro[i][j]<minpoz)
			{	
				minpoz=ro[i][j];
				xr=i;yr=j;
			}
}
	
void afis()
{
	ofstream out("rj.out",ofstream::out);
	out << minpoz<<" "<<xr<<" "<<yr;
	out.close();
}

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