Cod sursa(job #1005800)

Utilizator CosminnnChirica Cosmin Cosminnn Data 5 octombrie 2013 20:40:31
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <iostream>
#include <fstream>
#define Inf 2000

using namespace std;

int n ,m,st,dr,R[120][120],J[120][120],xr,yr,xj,yj,DistMin,xmin,ymin;
char M[120][120];

int dx[] = {-1,-1,0,1,1,1,0,-1};
int dy[] = {0,1,1,1,0,-1,-1,-1};

struct Element
{
    int x,y;
};
Element Q[10000],val;

inline void Read()
{
	ifstream f("rj.in");
	f>>n>>m;
	f.get();
	int i;
	for (i=1; i<=n; i++)
		f.getline((M[i]+1), 120);
	f.close();
}

inline void Bordare()
{
    int n1, i, m1;
	n1 = n + 1;
	m1 = m + 1;
	for (i = 0; i <= n1; i++)
		M[i][0] = M[i][m1] = 'X';
	for (i = 0; i <= m1; i++)
		M[0][i] = M[n1][i] = 'X';

}

inline void Initializare()
{
	int i,j;
	for( i = 1 ; i <= n ; ++i )
		for( j = 1 ; j <= m ; ++j )
			R[i][j] = J[i][j] = Inf;
}

inline void Search()
{
	int i,j;
	for( i = 1 ; i <= n ; ++i)
		for( j = 1  ; j <= m ; ++j )
		{
			if( M[i][j] == 'R' )
			{
				xr = i;
				yr = j;
			}
			if( M[i][j] == 'J' )
			{
				xj = i;
				yj = j;
			}
		}			
}

inline void Lee( int x, int y, int v[][120] )
{
	int coordx,coordy,i,j,k,d;
	st = 0;
	dr = 0;
	Q[dr].x = x;
	Q[dr].y = y;
	
	while( st <= dr )
	{
		coordx = Q[st].x;
		coordy = Q[st].y;
		d = v[coordx][coordy];
		st++;
		
		for( k = 0 ; k < 8 ; ++k )
		{
			i = coordx + dx[k];
			j = coordy + dy[k];
			if( M[i][j] != 'X' && (v[i][j] > d + 1) )
			{
				dr++;
				Q[dr].x = i;
				Q[dr].y = j;
				v[i][j] = d + 1;
			}
		}
	}
}



inline void Solve()
{
	int i,j;
	DistMin = Inf;
	
	Read();
	Bordare();
	Initializare(); 
	Search();
	
	R[xr][yr] = 1;
	J[xj][yj] = 1;
	
	Lee(xr,yr,R);
	Lee(xj,yj,J);
	
	for ( i = 1 ; i <= n; ++i )
	{
		for( j = 1 ; j <= m ; ++j )
		{
			if (R[i][j] == J[i][j] && DistMin > R[i][j] )
			{
				DistMin = R[i][j];
				xmin = i;
				ymin = j;
			}
		}
	}
	
/*	for( i = 0 ; i <= n+1 ; ++i )
	{	
		cout<<M[i]<<"\n";
	}
	for(i = 1  ; i <= n; ++i)
	{
		for( j = 1 ; j <= m; ++j )
		{
			if (R[i][j] != 2000)
				cout<<R[i][j]<<" ";
			else
				cout<<"x ";
		}
		cout<<"\n";
	}
	cout<<"\n";
	for(i = 1  ; i <= n; ++i)
	{
		for( j = 1 ; j <= m; ++j )
		{
			if (J[i][j] != 2000)
				cout<<J[i][j]<<" ";
			else
				cout<<"x ";
		}
		cout<<"\n";
	}
	cout<<"\n";*/
	ofstream g("rj.out");
	g<<DistMin<<" "<<xmin<<" "<<ymin<<"\n";
	g.close();
	
}
int main()
{
    Solve();
    return 0;
}